796. 旋转字符串
题目描述
输入两个字符串 s 和 goal。
一次旋转是指把 s 的第一个字符挪到末尾。例如 "abcde" 旋转一次得到 "bcdea"。
如果对 s 旋转若干次（可以是 0 次）后能得到 goal，返回 true，否则返回 false。
示例 1
输入：s = "abcde", goal = "cdeab" 输出：true
解释："abcde" 旋转一次得到 "bcdea"，再旋转一次得到 "cdeab"，正好等于 goal。
示例 2
输入：s = "abcde", goal = "abced" 输出：false
解释："abcde" 的 5 种旋转结果是 "abcde"、"bcdea"、"cdeab"、"deabc"、"eabcd"，其中没有 "abced"。
数据范围
1 <= s.length, goal.length <= 100s和goal只含小写英文字母。
解题思路：拼接 s + s 后查找子串
把 s 旋转 k 次得到 s[k:] + s[:k]。把 s 自己拼接一次得到 s + s，它从下标 k 开始的长度为 n 的片段恰好就是 s[k:] + s[:k]。所以 s 的所有旋转都是 s + s 的子串。先确认两串长度相同，再判断 goal 是否在 s + s 中出现。
为什么正确
长度为 n 的串 goal 是 s 的某个旋转，当且仅当它是 s + s 的一个子串。
复杂度分析
时间 O(n²)（朴素子串查找，用 KMP 可降到 O(n)），额外空间 O(n)。
易错点
忘记比较长度会出错：s = "aa"，goal = "a" 时 goal 是 s + s 的子串，但不是 s 的旋转。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
doubled = s + s
return goal in doubledclass Solution {
public boolean rotateString(String s, String goal) {
if (s.length() != goal.length()) {
return false;
}
String doubled = s + s;
return doubled.contains(goal);
}
}class Solution {
public:
bool rotateString(string s, string goal) {
if (s.size() != goal.size()) {
return false;
}
string doubled = s + s;
return doubled.find(goal) != string::npos;
}
};func rotateString(s string, goal string) bool {
if len(s) != len(goal) {
return false
}
doubled := s + s
return strings.Contains(doubled, goal)
}var rotateString = function(s, goal) {
if (s.length !== goal.length) {
return false;
}
const doubled = s + s;
return doubled.includes(goal);
};function rotateString(s: string, goal: string): boolean {
if (s.length !== goal.length) {
return false;
}
const doubled = s + s;
return doubled.includes(goal);
}其他解法
内置查找写法最短，最坏 O(n²)；KMP 把匹配降到 O(n)，适合长字符串或不能用库函数的场合。
解法 2：s + s 上的 KMP 匹配 时间 O(n)，空间 O(n)
同样利用“goal 是 s 的旋转 ⇔ 长度相等且 goal 是 s + s 的子串”。先求 goal 的前缀函数 fail[i]（goal[0..i] 最长的相等真前缀和真后缀长度），再在 s + s 上扫描：字符相等就前进，不等就把已匹配长度回退到 fail[j - 1]，文本指针从不后退。匹配长度达到 n 即为旋转。
最坏情况也是线性时间，不依赖语言内置查找的实现。本题 n ≤ 100，内置查找已经足够，KMP 代码更长，价值在于练习字符串匹配的通用技巧。
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
n = len(s)
if n != len(goal):
return False
fail = [0] * n
j = 0
for i in range(1, n):
while j > 0 and goal[i] != goal[j]:
j = fail[j - 1]
if goal[i] == goal[j]:
j += 1
fail[i] = j
text = s + s
j = 0
for c in text:
while j > 0 and c != goal[j]:
j = fail[j - 1]
if c == goal[j]:
j += 1
if j == n:
return True
return Falseclass Solution {
public boolean rotateString(String s, String goal) {
int n = s.length();
if (n != goal.length()) return false;
int[] fail = new int[n];
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && goal.charAt(i) != goal.charAt(j)) j = fail[j - 1];
if (goal.charAt(i) == goal.charAt(j)) j++;
fail[i] = j;
}
String text = s + s;
int j = 0;
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
while (j > 0 && c != goal.charAt(j)) j = fail[j - 1];
if (c == goal.charAt(j)) j++;
if (j == n) return true;
}
return false;
}
}class Solution {
public:
bool rotateString(string s, string goal) {
int n = s.size();
if (n != (int)goal.size()) return false;
vector<int> fail(n, 0);
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && goal[i] != goal[j]) j = fail[j - 1];
if (goal[i] == goal[j]) j++;
fail[i] = j;
}
string text = s + s;
int j = 0;
for (char c : text) {
while (j > 0 && c != goal[j]) j = fail[j - 1];
if (c == goal[j]) j++;
if (j == n) return true;
}
return false;
}
};func rotateString(s string, goal string) bool {
n := len(s)
if n != len(goal) {
return false
}
fail := make([]int, n)
for i, j := 1, 0; i < n; i++ {
for j > 0 && goal[i] != goal[j] {
j = fail[j-1]
}
if goal[i] == goal[j] {
j++
}
fail[i] = j
}
text := s + s
j := 0
for i := 0; i < len(text); i++ {
for j > 0 && text[i] != goal[j] {
j = fail[j-1]
}
if text[i] == goal[j] {
j++
}
if j == n {
return true
}
}
return false
}var rotateString = function(s, goal) {
const n = s.length;
if (n !== goal.length) return false;
const fail = new Array(n).fill(0);
for (let i = 1, j = 0; i < n; i++) {
while (j > 0 && goal[i] !== goal[j]) j = fail[j - 1];
if (goal[i] === goal[j]) j++;
fail[i] = j;
}
const text = s + s;
let j = 0;
for (const c of text) {
while (j > 0 && c !== goal[j]) j = fail[j - 1];
if (c === goal[j]) j++;
if (j === n) return true;
}
return false;
};function rotateString(s: string, goal: string): boolean {
const n = s.length;
if (n !== goal.length) return false;
const fail: number[] = new Array(n).fill(0);
for (let i = 1, j = 0; i < n; i++) {
while (j > 0 && goal[i] !== goal[j]) j = fail[j - 1];
if (goal[i] === goal[j]) j++;
fail[i] = j;
}
const text = s + s;
let j = 0;
for (const c of text) {
while (j > 0 && c !== goal[j]) j = fail[j - 1];
if (c === goal[j]) j++;
if (j === n) return true;
}
return false;
}