RotateString [source code]

public class RotateString {
static
/******************************************************************************/
class Solution {
    public boolean rotateString(String A, String B) {
        return (A + A).contains (B);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        RotateString.Solution tester = new RotateString.Solution();
    }
}

比较简单的题目, circular的常规处理方法;

速度是4ms (NA).

editorial

Approach #1: Brute Force [Accepted]

Intuition

For each rotation of A, let's check if it equals B.

Algorithm

More specifically, say we rotate A by s. Then, instead of A[0], A[1], A[2], ..., we have A[s], A[s+1], A[s+2], ...; and we should check that A[s] == B[0], A[s+1] == B[1], A[s+2] == B[2], etc.

class Solution {  
    public boolean rotateString(String A, String B) {  
        if (A.length() != B.length())  
            return false;  

        search:  
            for (int s = 0; s < A.length(); ++s) {  
                for (int i = 0; i < A.length(); ++i) {  
                    if (A.charAt((s+i) % A.length()) != B.charAt(i))  
                        continue search;  
                }  
                return true;  
            }  
        return false;  
    }  
}

我自己的做法, 因为用了contains, 所以最后的情况还是看contains是怎么实现的, 然后这个又回到了重新实现KMP的问题上面了; 所以KMP这个背下来真的重要;

Approach #2: Rolling Hash [Accepted]

This approach will be added soon.

Approach #3: KMP (Knuth-Morris-Pratt) [Accepted]

This approach will be added soon.

之前好像有一道更难的, 是一个可以不停wrap的, 那个就是最后用fancy wheels的思路, 用KMP来实现这个查找功能, 最后优化复杂度;

https://leetcode.com/problems/rotate-string/discuss/118696/C++-Java-Python-1-Line-Solution

public boolean rotateString(String A, String B) {  
    return A.length() == B.length() && (A + A).contains(B);  
}

突然发现我上面的解法实际上不对, 要判断长度的; 这个失误有点丢人;

uwi:

class Solution {  
    public boolean rotateString(String A, String B) {  
        if(A.length() != B.length())return false;  
        return (A+A).indexOf(B) >= 0;  
    }  
}

果然大神还是大神;

Problem Description

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.

Example 1:  
Input: A = 'abcde', B = 'cdeab'  
Output: true  

Example 2:  
Input: A = 'abcde', B = 'abced'  
Output: false

Note:

• A and B will have length at most 100.

Difficulty:Easy
Total Accepted:4.7K
Total Submissions:7K
Contributor:ngoc_lam