【第三轮】6.23-6.29 CareerCup 1.8

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

请问两个问题：
1. 即使用了StringBuilder或者是StringBuffer为啥时间复杂度是O(1)呢？我觉得就算用了StringBuilder虽然在连接字符串的时候不用new新对象，但是仍然需要进行字符串copy工作啊，应该还是O(n)啊。

2. 为啥空间复杂度是O(1)呢？不应该也是O(n)

Idea: Same idea as the Cracking the Coding Interview book.

First, if the s2 is the rotation of s1, they should have the same length.
Then, s2 should be a subString of s1 + s1
Time Complexity: O(n)
Space Complexity: O(n)

Code Link: http://www.jyuan92.com/post-371

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.

锦木千束 发表于 2014-6-23 06:06
【解题思路】首先检查俩字符串等长，然后检查S2是不是S1+S1的子串
【时间复杂度】不考虑isSub ...

isSubString的实现可以用String.contains，但是Oracle好像没有给String.contains的源代码？

如果用KMP的方法，好像Time Complexity是O(n)
如果用naive implementation，就是O(N^2)了

wilbert 发表于 2014-6-23 12:53
【解题思路】
Check if s2 is the substring of s1+s1
【时间复杂度】

空间复杂度应该是O(n)吧，n决定于s1的长度