796. Rotate String

• 796. Rotate String
  • Description
  • Intuition
  • Pitfall
  • Solution

Description

Here

Intuition

We are given two strings, A and B.

A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = 'abcde', then it will be 'bcdea' after one shift on A. Return True if and only if A can become B after some number of shifts on A.

If we can add A + A, we can use A.length() == B.length() && (A + A).substring(B) to determine the result by applying KMP

Pitfall

1. 需要检查A和B的长度
2. 在KMP模板中，需要严格遵守 int i = 0, j = 0，并在外面比较 -> 否则，"" and "" 这个case过不去

  public boolean rotateString(String A, String B) {
    if (A.length() != B.length()) {
      return false;
    }
    final String s = A + A, p = B;
    final int[] next = getNext(p);
    int i = 0, j = 0;
    for (; i < s.length() && j < p.length(); ) {
      if (j == -1 || s.charAt(i) == p.charAt(j)) {
        ++i;
        ++j;
        if (j == p.length()) {
          return true;
        }
      } else {
        j = next[j];
      }
    }
    return j == p.length();
  }

  static int[] getNext(final String p) {
    final int[] next = new int[p.length()];
    if (p.length() == 0) {
      return next;
    }
    next[0] = -1;
    for (int k = -1, j = 0; j < p.length() - 1; ) {
      if (k == -1 || p.charAt(k) == p.charAt(j)) {
        k++;
        j++;
        next[j] = k;
      } else {
        k = next[k];
      }
    }
    return next;
  }

Solution

Solution