【第三轮】6.23-6.29 CareerCup 1.8

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、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

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

serolins 发表于 2014-6-22 20:40
【解题思路】
// So first think about the definition of Rotations
// first of all, the two string ...

我觉得用了Stringbuffer应该还是O(n)的time Complexity，因为在这道题中，String和StringBuffer没有区别，String的concentrate也只进行了一次……仅仅new了一个新的String而已……

There is no different about the Time and Space Complexity when using StringBuffer instead of String. Because each String concatenation has cost equal to the length of the combined string, but each StringBuilder append has (amortized) cost equal to the length of the appended string. A single String concatenation, as use here, is always linear-time, but it’s wise to switch to a StringBuilder for repeated appends, to avoid repaying the cost of the first characters many times over.

【解题思路】
这个题当时想了好久都没想出来，这次看见题立刻想起书上的答案了。。。
         * 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

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

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

真大神......

【解题思路】首先检查俩字符串等长，然后检查S2是不是S1+S1的子串
【时间复杂度】不考虑isSubstring的话。。 好像就是O（n）？  字符串相加不会算诶。。。
【空间复杂度】O（n）
【gist link】https://gist.github.com/weazord/0c7aac2ae0fc7bfc3497

【解题思路】首先检查俩字符串等长，然后检查S2是不是S1+S1的子串
【时间复杂度】不知道字符串相加的时间复杂度
【空间复杂度】O（n）
【gist link】https://gist.github.com/qiangusc/4c27e5a19379852144a5

fang_wu 发表于 2014-6-23 19:14
【解题思路】首先检查俩字符串等长，然后检查S2是不是S1+S1的子串
【时间复杂度】不知道字符串相加的时间 ...

求解空间为啥是O（n）?

//【解题思路】
//先找出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