一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1510|回复: 50
收起左侧

[CareerCup] 【第三轮】6.23-6.29 CareerCup 1.8

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-22 23:59:55 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 wrj5518 于 2014-6-23 09:31 编辑

1.8 Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (e.g.,"waterbottle"is a rotation of"erbottlewat").

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。
grassgigi 发表于 2014-6-23 02:14:01 | 显示全部楼层
【解题思路】
Concatenate s1 with itself, since there is a rotation, after concatenation s2 will be a sub string of s1+s1

【时间复杂度】
N = (s1+s1).length, M = s2.length
Concatenation takes O(N) time. Depends on the time complexity of isSubstring function:
Boyer-Moore: O(MN) worse, O(N/M) on average

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/779f7943a04cbb903575

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

heycinderella 发表于 2014-6-23 08:18:29 | 显示全部楼层
本帖最后由 heycinderella 于 2014-6-24 05:47 编辑

【解题思路】
这个题当时想了好久都没想出来,这次看见题立刻想起书上的答案了。。。
         * Same thinking process as in the book, if str2 is a rotation of str1, they
         * have to have the same length, and str1 is a substring of str2+str2
【时间复杂度】
O(n) if using String, O(1) if using StringBuilder, not counting the time of the isSubstring() method

【空间复杂度】
O(N)

【gist link】
https://gist.github.com/XiaoxiaoLi/dac23b167283bf509a34
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-6-23 09:40:09 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-23 10:41:34 | 显示全部楼层
【解题思路】如果s2是s1的rotation,那么s2一定是concat(s1,s1)的substring。再加上s1.length == s2.length的限制即可
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist link】https://gist.github.com/chouclee/a9946f058856cdbb73f5
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-23 12:23:43 | 显示全部楼层
grassgigi 发表于 2014-6-23 02:14
【解题思路】
Concatenate s1 with itself, since there is a rotation, after concatenation s2 will be  ...

真大神......
回复 支持 反对

使用道具 举报

aloncgo 发表于 2014-6-23 19:06:13 | 显示全部楼层
【解题思路】首先检查俩字符串等长,然后检查S2是不是S1+S1的子串
【时间复杂度】不考虑isSubstring的话。。 好像就是O(n)?  字符串相加不会算诶。。。
【空间复杂度】O(n)
【gist link】https://gist.github.com/weazord/0c7aac2ae0fc7bfc3497
回复 支持 反对

使用道具 举报

fang_wu 发表于 2014-6-23 19:14:52 | 显示全部楼层
【解题思路】首先检查俩字符串等长,然后检查S2是不是S1+S1的子串
【时间复杂度】不知道字符串相加的时间复杂度
【空间复杂度】O(n)
【gist link】https://gist.github.com/qiangusc/4c27e5a19379852144a5
回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-6-24 00:02:24 | 显示全部楼层
fang_wu 发表于 2014-6-23 19:14
【解题思路】首先检查俩字符串等长,然后检查S2是不是S1+S1的子串
【时间复杂度】不知道字符串相加的时间 ...

求解空间为啥是O(n)?
回复 支持 反对

使用道具 举报

Tsien 发表于 2014-6-24 00:19:10 | 显示全部楼层
//【解题思路】
//先找出s1第一个字符在s2中的位置pos,将s2[0...pos]作为word参数传给isString
//判断它是否为s1的子串,若是,则s2是s1的rotation
//【时间复杂度】
//O(n)
//【空间复杂度】
//O(k), k 为子串长度
//【gist link】
https://gist.github.com/Tsien/a39a2edf6c4535eba329
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-6-24 00:45:30 | 显示全部楼层
heycinderella 发表于 2014-6-24 00:02
求解空间为啥是O(n)?

Cuz string type is immutable, so concatenation creates new string object.
回复 支持 反对

使用道具 举报

zhenzhenanan 发表于 2014-6-24 01:15:03 | 显示全部楼层
【解题思路】
好像是CTCI原题吧。
把两个s1连接起来变成一个新的string,我们叫它s3,然后我们用isSubstring来检查s2是否是s3的substring。
原理是:如果s2是s1的rotation,比如s1是:abcdefg,s2是:defgabc。那么当我们把两个s1连接起来之后,s3是:abcdefgabcdefg,可以看见,s2肯定是s3的substring。
【时间复杂度】
O(n),n是s1的长度。因为拷贝一个string虽然可能只需要一行代码,但背后的时间是O(n)。
【空间复杂度】
O(n), where n is the length of s1
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_8-cc
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
None.
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-24 01:53:16 | 显示全部楼层
【解题思路】
Check if s2 is the substring of s1+s1
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/77a2aa34ab66cdbbb4b5
回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-6-24 05:47:46 | 显示全部楼层
grassgigi 发表于 2014-6-24 00:45
Cuz string type is immutable, so concatenation creates new string object.

啊果然是这样,之前没想到,谢谢!
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-24 07:19:44 | 显示全部楼层
【解题思路】
Check if s2 is the substring of s1+s1
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/hilda8519/34e3624fa25453ccbaa7

按书做的
回复 支持 反对

使用道具 举报

pud 发表于 2014-6-24 08:34:45 | 显示全部楼层
【解题思路】
看答案提示的,检查s2是不是s1+s1的substring
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/yokiy/27b7f31ff00ffcc4f896
回复 支持 反对

使用道具 举报

fang_wu 发表于 2014-6-24 10:05:53 | 显示全部楼层
heycinderella 发表于 2014-6-24 00:02
求解空间为啥是O(n)?

s1+s1,就会开通s1的空间
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-6-24 12:31:02 | 显示全部楼层
本帖最后由 jason51122 于 2014-6-24 12:50 编辑

【解题思路】Concat 2 str1 together as str. Find if str2 is a substring of str.
【时间复杂度】O(N^2) str.indexOf(str1) is O(N^2)
【空间复杂度】O(N) str = str1 + str1
【gist link】https://gist.github.com/jason51122/6f636b270039087a41ce
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-6-24 13:02:41 | 显示全部楼层
本帖最后由 jason51122 于 2014-6-24 13:06 编辑
heycinderella 发表于 2014-6-23 08:18
【解题思路】
这个题当时想了好久都没想出来,这次看见题立刻想起书上的答案了。。。
         * Same th ...

Suppose the length of string is N. I think append() operation for StringBuffer will cost 2N, which is O(N).
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-24 15:05:20 | 显示全部楼层
grassgigi 发表于 2014-6-23 02:14
【解题思路】
Concatenate s1 with itself, since there is a rotation, after concatenation s2 will be  ...

bm的空间是n
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 06:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表