【第三轮】6.23-6.29 CareerCup 1.8

heycinderella 发表于 2014-6-24 00:02
求解空间为啥是O（n）?

Cuz string type is immutable, so concatenation creates new string object.

【解题思路】
好像是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.

【解题思路】
Check if s2 is the substring of s1+s1
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/77a2aa34ab66cdbbb4b5

grassgigi 发表于 2014-6-24 00:45
Cuz string type is immutable, so concatenation creates new string object.

啊果然是这样,之前没想到,谢谢!

【解题思路】
Check if s2 is the substring of s1+s1
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/hilda8519/34e3624fa25453ccbaa7

按书做的

【解题思路】
看答案提示的，检查s2是不是s1+s1的substring
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/yokiy/27b7f31ff00ffcc4f896

heycinderella 发表于 2014-6-24 00:02
求解空间为啥是O（n）?

s1+s1，就会开通s1的空间

【解题思路】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

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).

grassgigi 发表于 2014-6-23 02:14
【解题思路】
Concatenate s1 with itself, since there is a rotation, after concatenation s2 will be  ...

bm的空间是n