Cracking Coding Interview - 1.9 String Rotation

String Rotation: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 sl using only one call to isSubstring (e.g.,"waterbottle" is a rotation of "erbottlewat").

分析

注意看题目，rotation不是把字符串反转，而是找一个点，把前后颠倒一下。

解答1

能最简单的办法是弄个指针p遍历s1，用isSubstring判断s1[0~p]和s1[p+1~s1.length-1]是否都是s2的子串。但是这样的话isSubstring就调用了多次了，而题目要求只调用一次。

题目中给了暗示，isSubstring一般用在长短两个字符串上，但是这里我们的字符串长度是一样的，所以你可以想想看是不是把s1+s2，或者s1+s1，或者s2+s2。

如果s1是s2的rotation，那么你可以把s1看成两个部分xy，即s1=xy，则s2=yx。如果把s2 double一下，那么就变成了yxyx，然后你会发现s1就是它的子串。在这道题目中适当的抽象是必要的，比如xy这种。

1
2
3
4
5
6
7

public boolean isRotation(String s1, String s2) {
  if (s1.length() != s2.length()) {
    return false;
  }
  String s22 = s2 + s2;
  return isSubString(s1, s22);
}

时间复杂度：O(n)，假设isSubtstring是O(2n)，字符串串接是O(2n)

空间复杂度：O(n)，搞了个字符串，所以是O(2n)