题目描述

给定两个字符串A,B，判断B是否是由A翻转而得，例如”cdeab”是由”abcde”翻转而得。

样例

输入: A = 'abcde', B = 'cdeab'
输出: true

输入: A = 'abcde', B = 'abced'
输出: false

算法1

(字符串操作) $O(n^2)$

如果B可以由A翻转而得，那么B字符串一定是两个A首尾相接得到的字符串的子串，例如”cdeab”就是”abcdeabcde”的子串

时间复杂度分析：使用STL中string的find，最差的情况复杂度是$O(n^2)$。当然可以用KMP实现字符串查找，复杂度会降为O(n)

C++ 代码

class Solution {
public:
    bool rotateString(string A, string B) {
        if(A.size() != B.size())
            return false;
        A =A+A;
        return A.find(B)!=std::string::npos;        
    }
};