【第三轮】6.23-6.29 CareerCup 1.8

【解题思路】
boyer moore search
【时间复杂度】
N+M
【空间复杂度】
N
【gist link】https://gist.github.com/gaoyike/e1ce14a8dccc0a300159
【test case】

jason51122 发表于 2014-6-24 13:02
Suppose the length of string is N. I think append() operation for StringBuffer will cost 2N, which ...

你说的是时间还是空间？

【解题思路】
看书后按照书上的来，检查s2是不是s1s1的substring
【时间复杂度】
觉得这个得看你自己的假设了，如果没有实现isSubstring，可以把这个当做O(1)操作，同样concatenate操作也可以当做O(1)[c++ 里， string 的 operator += 操作]
如果实现了isSubstring, 那就得按具体的算法来计算。
【空间复杂度】
O(N)
【gist link】https://gist.github.com/xun-gong/7895504c829d08bba647

【解题思路】
自己没想出来=。=看了书上解答之后茅塞顿开……
if s1 and s2 have same length and s2 is substring of s1s1, then s2 must be a rotation of s1!
为了方便test还自己写了个isSubstring呼……
【时间复杂度】
O(N^2) (subString)
【空间复杂度】
O(N) (concatenation)
【gist link】
https://gist.github.com/f58495f1e17061d43c53
【test case】
empty string -> return false

readman 发表于 2014-6-24 15:05
bm的空间是n

I think it is O(R), in which R is size of the character set.But you are correct that the total space complexity will be O(n)

heycinderella 发表于 2014-6-25 00:28
你说的是时间还是空间？

Time Complexity

jason51122 发表于 2014-6-24 13:02
Suppose the length of string is N. I think append() operation for StringBuffer will cost 2N, which ...

啊是我代码的问题，要是这样写是否是O(1)呢?我实在不太会算。。。谢谢！
return isSubstring(str1, (new StringBuilder(str2)).append(str2).toString());

【解题思路】
My 1st idea is to use recursion. However this disobeys 'using only one call to isSubstring'.
【时间复杂度】Top-level O(N)
【空间复杂度】O(1)
【gist link】
....

heycinderella 发表于 2014-6-26 01:21
啊是我代码的问题，要是这样写是否是O(1)呢?我实在不太会算。。。谢谢！
return isSubstring(str1, (new ...

Suppose the length of str2 is N. new StringBuffer(str2) will cost N. append(str2) will also cost N. Please refer http://stackoverflow.com/questio ... mple-piece-of-code. Thanks.

【解题思路】 rotation可能是S1=S2，或者S1被拦腰截断，后段在前面，前段在后面，所以只要S1+S1,就能囊括rotation的各种可能。rotation结果S2是S1+S1的substring。
【时间复杂度】
O(n)
【空间复杂度】
O(n) 多了一段s1.

地址 https://gist.github.com/guchang/cdf6826ecab11093548e