Java C++题解leetcode字符串轮转KMP算法详解

1. 题目描述

给定两个字符串s1和s2，判断s2是否可以通过将s1中的某个子串移动后得到。

2. 思路分析

2.1 暴力枚举

我们可以将s1分为两段，任选一段放到另一段的前面，再判断是否与s2相等，如此循环往复。但是这样的时间复杂度为$O(n^2)$。

2.2 KMP算法

我们可以利用KMP算法来解决该问题，KMP算法是一种字符串匹配算法。我们可以将s1与s2进行拼接，判断s1+s1是否包含s2子串即可。

3. 代码实现

3.1 暴力枚举

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1 == null || s2 == null) return false;
        if (s1.length() != s2.length()) return false;
        if (s1.equals(s2)) return true;
        for (int i = 1; i < s1.length(); i++) {
            String s = s1.substring(i) + s1.substring(0, i);
            if (s.equals(s2)) return true;
        }
        return false;
    }
}

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;
        for (int i = 1; i < s1.size(); i++) {
            string s = s1.substr(i) + s1.substr(0, i);
            if (s == s2) return true;
        }
        return false;
    }
};

3.2 KMP算法

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1 == null || s2 == null) return false;
        if (s1.length() != s2.length()) return false;
        return (s1 + s1).indexOf(s2) != -1;
    }
}

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        return (s1 + s1).find(s2) != string::npos;
    }
};

4. 测试样例

输入: s1 = "waterbottle", s2 = "erbottlewat"
输出: true

输入：s1 = "abcde", s2 = "cdeab"
输出：true

以上两组测试数据分别证明了暴力枚举和KMP算法的正确性，并且KMP算法的时间复杂度更小。