P221 旋转字符串

描述#

这个题目说的是，给你两个字符串 A 和 B，你要判断字符串 A 是否可以通过将左边的若干字符旋转到右边，来得到字符串 B。如果可以就返回 true，否则返回 false。

比如说，给你的两个字符串是：
A = "abcde"
B = "cdeab"
你可以先将 "abcde" 最左边的 a 旋转到右边，然后再把 b 旋转到右边，就可以把字符串 A 变成字符串 B。因此返回 true。
再比如说，给你的两个字符串是：
A = "abcde"
B = "abced"
那么 A 就无法通过将左边的若干字符旋转到右边，来得到字符串 B。因此你要返回 false。

相关视频：实现 strstr

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(1)
  public boolean rotateStringBuiltinMethod(String A, String B) {
    return A.length() == B.length() && (A + A).contains(B);
  }

  // Time: O(n^2), Space: O(1)
  public boolean rotateStringStrStr(String A, String B) {
    if (A.length() != B.length()) return false;
    String AA = A + A;
    int n = A.length(), nn = 2 * n;
    for (int start = 0; start <= n; ++start) {
      int i = start, j = 0;
      while (i < nn && j < n && AA.charAt(i) == B.charAt(j)) {
        ++i; ++j;
      }
      if (j == n) return true;
    }
    return false;
  }

}