【第三轮】6.23-6.29 CareerCup 1.8

【解题思路】
Check if s1.length()==s2.length() && s2 is the substring of s1s1
【时间复杂度】
O(N)
* 拷贝一个string虽然可能只需要一行代码，但背后的时间是O(n)
【空间复杂度】
O(N)
* 需要一个新的字符串
【gist link】
https://gist.github.com/JoyceeLee/7ec271e0693d5e6d9601

【解题思路】check s2 if a substring of s1+s1
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/bitcpf/e42630e11005bf25c241

jason51122 发表于 2014-6-26 12:58
Suppose the length of str2 is N. new StringBuffer(str2) will cost N. append(str2) will also cost N ...

谢谢！

【解题思路】  check if s1 is a substring of s2s2
【时间复杂度】O(N) for concatenate + time for isSubstring   
if we use StringBuffer  time for concatenate should be O(1)
【空间复杂度】 O(N)    create a new String
【gist link】  https://gist.github.com/jyhjuzi/1b818b85eeff95152460

============================================================================
Solution        : Concatenate s1 with s1, check if s2 is a substring of s1 + s1
Time Complexity : Depend on isSubstring()
Space Complexity: O(n)
Gist Link       : https://gist.github.com/habina/33b581c69f59fccfc1a6
============================================================================

============================================================================
Solution        : Concatenate s1 with s1, check if s2 is a substring of s1 + s1
Time Complexity : Depend on isSubstring()
Space Complexity: O(n)
Gist Link       : https://gist.github.com/habina/33b581c69f59fccfc1a6
============================================================================

【解题思路】
if s2 is a rotation of s1, s2 must be a sub string of s1+s1
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist link】https://gist.github.com/JoshuaTang/e6f9e1f33dfc83d4d8f9

【解题思路】The rotation would not change the length of the string, so first check the length of the two strings. Then, if s2 is a rotation of s1, we could divide s1 into to parts, str1str2, where the breakpoint is where rotation appear. Then s2 should be str2str1. If we append s2 to itself, we would get a str2str1str2str1 = str2s1str1, where s1 should be a substring of it. This is just what we want.
【时间复杂度】The append process is O(N), so the true time complexity depends on the isSubstring() function
【空间复杂度】O(N)
【gist link】
https://gist.github.com/98c5940bf857352abbc2.git
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

自己手写的KMP，不知道有没有BUG

【解题思路】
If str2 is a rotation of str1, str2 must be a substring of str1 + str1.


【时间复杂度】
O(n)
n is the length of str1

【空间复杂度】
O(n)
n is the length of str1

【gist link】
https://gist.github.com/happyWinner/d9acddf8288676fe10f8

【解题思路】check whether s1 is (s2+s2)'s substring.
【时间复杂度】o(n)
【空间复杂度】o(1)
【gist link】
https://gist.github.com/jaly50/5f1f5538fe6fa6283ba6
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
"waterbottle!" is a rotation of "erbottle!wat": true