LeetCode 面试题 01.09. 字符串轮转

2023-02-24 HGNULB 约 10 分钟

文章信息 7 个分类 2 个标签

分类

LeetCode CodeTop 简单未解决 1-2 字节跳动程序员面试金典（第 6 版）

题目描述

✅ 面试题 01.09. 字符串轮转

题意分析

「轮转」的定义是：把 s2 在某个位置切成前后两段 x 与 y，再交换两段拼回去得到 s1，即 s2 = x + y 且 s1 = y + x。换句话说要判断 s1 能否由 s2 循环左移若干位得到。注意切点的位置不给定，需要我们自己考虑全部可能。

题目最特别的约束是「只能调用一次 isSubstring 方法」——一个用于判断某字符串是否是另一字符串子串的检查函数。这条限制既是禁令也是提示：它明确排除了「枚举每个切点各查一次」的做法，同时把答案框死在「构造出某个字符串，然后做且仅做一次子串查询」的形状上。看到「只允许一次查询」这类措辞，就该往「把所有情况打包进一个更大的对象里一次性判定」的方向想。

另一个隐含约束是：轮转不改变字符的种类和数量，也不改变字符之间的循环相邻关系，因此长度不同的两个串一定不是轮转关系。这个判断不消耗子串查询次数，可以放心前置。

边界上要注意：切点可以取在两端，此时 x 或 y 为空串，轮转结果就是 s2 本身，所以 s1 == s2 属于合法的轮转；两个空串也应返回真；s1 与 s2 长度相同但字符组成不同时必须返回假。

还要留意长度相等这一前提对后续推理是必不可少的：脱离它，「是子串」并不能反推出「是轮转」。

解法：拼接包含判断

核心思路

暴力做法很自然：枚举切点 i 从 0 到 n - 1，每次把 s2 拆成 s2[0..i) 与 s2[i..n) 再拼成 s2[i..n) + s2[0..i)，与 s1 逐字符比较。这是 $O(n^2)$ 的时间，更致命的是它需要 n 次独立判定，直接违反「只能调用一次子串检查」的规则。

瓶颈在于把 n 种切点当成了 n 个互不相干的问题，每个都要单独验证一次。有没有办法把这 n 种可能塞进同一个对象里？

关键观察来自轮转的循环性：所有轮转结果都可以看成在一个首尾相接的环上，从不同起点读满 n 个字符得到的串。而把这个环「剪开并展平」的标准手法，就是把串复制一份接在自己后面。考察 s2 + s2 这个长度为 2n 的串：它的下标 i 开始、长度为 n 的子串恰好是 s2[i..n) + s2[0..i)，也就是切点为 i 的那个轮转结果，i 取遍 0 到 n - 1 时不重不漏地覆盖了全部 n 种轮转。

于是得到本题的核心不变量：当 |s1| == |s2| == n 时，s1 是 s2 的轮转，当且仅当 s1 是 s2 + s2 的子串。

必要性方向：若 s1 是轮转，设 s2 = x + y、s1 = y + x，那么 s2 + s2 = x + y + x + y，中间的 y + x 正是 s1，所以 s1 出现在偏移量为 |x| 的位置上。充分性方向：若 s1 出现在 s2 + s2 的下标 i 处，因为 s1 长度为 n 而母串长度为 2n，必有 0 <= i <= n；取 x = s2[0..i)、y = s2[i..n)，则该位置往后 n 个字符恰好是 y + x，正好证明 s1 是 s2 的轮转。这里长度相等是充分性成立的关键——若 s1 更短，它可能只是某段局部片段而不构成完整轮转。

有了这条等价关系，n 次判定被压缩成一次子串查询，既满足了题目对调用次数的限制，也把时间降到线性（子串查询用 KMP 或类似线性算法实现时）。

解题步骤

先比较长度，不等直接返回假。这一步不使用子串查询，因此不消耗宝贵的唯一一次调用机会；同时它是后面等价关系成立的前提，必须前置而不能省略。若长度不等仍去做拼接查询，短的那个串完全可能作为片段命中，得出错误的真。

单独处理两个空串的情况，返回真。空串轮转后仍是空串，答案显然为真；显式写出这一分支是为了绕开某些语言中「空串是否算作任意串的子串」的语义分歧，让结果不依赖库函数的约定。

构造 doubled = s1 + s1。这是整个解法的核心操作，把「n 种切点」物化成一个长度为 2n 的母串，使得所有轮转结果同时以子串形式存在于其中。这里拼接的是 s1 还是 s2 并不影响正确性，因为轮转关系是对称的：s1 是 s2 的轮转等价于 s2 是 s1 的轮转，反向代入上面的证明即可。

做且仅做一次子串查询，判断 s2 是否出现在 doubled 中，直接返回结果。查询只调用一次，符合题目限制；命中即说明存在某个切点使得轮转成立，未命中则说明所有切点都不成立，无需再做任何补充判断。

不要在此之后追加任何额外的字符统计或二次校验。上面的等价关系是充要的，命中就一定是轮转，多余的校验既无必要，也可能因为写错而引入假阴性。

以 s1 = "waterbottle"、s2 = "erbottlewat" 走一遍。

第一步比长度：s1 长度 11，s2 长度 11，相等，继续。第二步判空：非空，继续。

第三步拼接：doubled = "waterbottle" + "waterbottle" = "waterbottlewaterbottle"，长度 22。

第四步查询 s2 = "erbottlewat" 是否是 doubled 的子串。手工定位：doubled 的下标从 0 开始是 w(0) a(1) t(2) e(3) r(4) b(5) o(6) t(7) t(8) l(9) e(10) w(11) a(12) t(13) e(14) r(15) ...。从下标 3 开始取 11 个字符，依次是 e、r、b、o、t、t、l、e、w、a、t，拼起来正是 "erbottlewat"，与 s2 完全一致，查询命中，返回 true。

反向验证一下这个偏移量的含义：命中位置 i = 3，对应 x = s1[0..3) = "wat"、y = s1[3..11) = "erbottle"，于是 y + x = "erbottle" + "wat" = "erbottlewat" 正是 s2，确实是一次合法轮转。

再看一个反例 s1 = "aa"、s2 = "ab"：长度都是 2，doubled = "aaaa"，在其中查找 "ab"，四个字符全是 a，任何长度为 2 的子串都是 "aa"，查询未命中，返回 false，符合预期。

最后看一个相等的情形 s1 = "abc"、s2 = "abc"：doubled = "abcabc"，"abc" 出现在下标 0 处，命中返回 true，对应切点 i = 0 即 x 为空串、y 为整串的平凡轮转，题意允许，答案正确。

代码实现

// 若长度相同，则 s2 是 s1 + s1 的子串当且仅当是轮转字符串。
class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        if (s1.isEmpty()) {
            return true;
        }

        String doubled = s1 + s1;
        return doubled.contains(s2);
    }
}

// 若长度相同，则 s2 是 s1 + s1 的子串当且仅当是轮转字符串。
import "strings"

func isFlipedString(s1 string, s2 string) bool {
	if len(s1) != len(s2) {
		return false
	}
	if len(s1) == 0 {
		return true
	}

	doubled := s1 + s1
	return strings.Contains(doubled, s2)
}

复杂度分析

时间复杂度：设一次 isSubstring 的代价为 $T(2n,n)$，总时间是 $O(n)+T(2n,n)$：构造倍长串需要 $O(n)$，随后只查询一次。若面试约定 isSubstring 使用 KMP 等线性匹配，整体为 $O(n)$；本文 Java/Go 代码调用标准库，而标准库接口没有承诺具体匹配算法，因此严格讨论最坏情况时不应把它无条件写成 $O(n)$。

空间复杂度：$O(n)$，倍长串占用线性空间。若把子串查询实现为 KMP，前缀函数同样需要 $O(n)$，总量级不变。

关键点总结

「只允许调用一次」是把 n 个子问题打包成一个的信号：题目限制查询次数时，几乎总是在暗示存在某种构造，能让所有候选情况在同一个对象里同时被检验。遇到「只能用一次某操作」先别急着优化循环，先想怎么合并问题。

倍长是处理环形结构的通用手法：把序列复制一份接在自己后面，环上「从任意起点读满一圈」就变成了线性串上「取任意长度为 n 的窗口」。这条技巧在环形数组、环形子数组最大和、环形队列等题里反复出现，不局限于字符串。

等价关系要双向证明：只说「轮转 ⇒ 是子串」不够，还要说明「是子串 ⇒ 轮转」，而后者依赖长度相等这一前提。面试时把两个方向都讲一遍，等于当场证明了算法正确性，比列举几个例子有说服力得多。

不消耗受限资源的前置判断要尽量前置：长度比较不算子串查询，放在最前面既能快速剪枝，又建立了后续推理的前提。凡是题目对某种操作计次时，先盘点哪些判断是「免费」的。

轮转关系是对称的：拼 s1 找 s2 与拼 s2 找 s1 完全等价，因为 s1 = y + x 与 s2 = x + y 互为对方的轮转。理解这一点可以避免在写代码时纠结拼哪个。

面试视角：若被追问严格线性复杂度，可把唯一一次子串查询实现为 KMP：对模式串求前缀函数，再扫描倍长串。还可以用 s1[i % n] 模拟倍长串，省掉拼接串；KMP 的前缀函数仍占 $O(n)$ 空间。

易错点总结

错误写法：省略长度相等的前置判断。用例 s1 = "abcde", s2 = "cd" → doubled = "abcdeabcde" 确实包含 "cd"，返回 true，但两串长度不同根本不可能是轮转关系，正确答案是 false。子串关系只有在长度相等时才等价于轮转。

错误写法：把长度判断写成 if (s1.length() < s2.length()) return false; 只挡一个方向。用例 s1 = "ab", s2 = "abab" → 长度 2 小于 4 会被挡住，但反过来 s1 = "abab", s2 = "ab" 时通过检查，doubled = "abababab" 包含 "ab"，错误返回 true。必须用不等号 != 双向拦截。

错误写法：拼接后查找的方向反了，写成 s2.contains(s1) 而没有拼接 s2。用例 s1 = "waterbottle", s2 = "erbottlewat" → 在长度 11 的 s2 里找长度 11 的 s1，只有完全相等才可能命中，此处不等返回 false，正确答案是 true，把所有非平凡轮转全判成了假。

错误写法：拼接的是两个不同的串，写成 s1 + s2 再查 s2。用例 s1 = "aa", s2 = "ab" → doubled = "aaab" 包含 "ab"，返回 true，但 "ab" 显然不是 "aa" 的轮转（字符组成都不同），返回了假阳性。必须是同一个串自我倍长。

错误写法：枚举每个切点各做一次子串查询或字符串比较。用例任意长度 11 的输入 → 逻辑上能算对，但调用了 11 次判定，违反题目「只能调用一次 isSubstring」的硬性限制，在面试中会被直接判定为没读懂题；同时复杂度退化为 $O(n^2)$。

错误写法：认为 s1 与 s2 完全相等时不算轮转，加一句 if (s1.equals(s2)) return false;。用例 s1 = "abc", s2 = "abc" → 正确答案是 true，因为切点取在两端（x 为空串）是合法轮转；加了这个短路会把最简单的用例判错。

错误写法：漏掉两个空串的处理并依赖库函数默认行为。用例 s1 = "", s2 = "" → 大多数语言中空串是任意串的子串会返回 true，但若代码里先做了 doubled.substring(1) 之类的下标操作，会抛越界异常。显式写 if (s1.isEmpty()) return true; 让行为不依赖实现约定。

错误写法：改用字符计数或排序后比较来判断。用例 s1 = "abcd", s2 = "abdc" → 两者字符组成完全相同，计数法与排序法都会返回 true，但 "abdc" 无法由 "abcd" 循环移位得到，正确答案是 false。字符多重集相同只是轮转的必要条件，不是充分条件。

错误写法：在循环里反复用 + 拼接构造倍长串。用例长度 10^4 的字符串 → Java 中 String 不可变，循环内每次 + 都新建一个对象并复制全部字符，累计 $O(n^2)$ 的复制量与大量垃圾对象，容易超时。一次性写 s1 + s1 或用 StringBuilder 即可。

错误写法：把标准库 contains 的复杂度当成语言层面的线性保证。构造倍长串只需 $O(n)$，但总复杂度还取决于子串匹配实现；面试官要求严格 $O(n)$ 时，应明确使用 KMP，而不是只改复杂度标注。

相似题目

题目	难度	考察点
796. 旋转字符串	简单	与本题同构但不限制调用次数，可用来对比枚举切点与倍长拼接两种写法的差距
28. 找出字符串中第一个匹配项的下标	简单	要求返回匹配下标而非布尔值，是本题背后子串查询的手写实现，考察 KMP 本身
459. 重复的子字符串	简单	同样用倍长拼接，但要掐头去尾在 `(s+s)[1:-1]` 中找 s，考察为何必须去掉两端
剑指 Offer 58 - II. 左旋转字符串	简单	给定移位数直接构造轮转结果而非判定，考察三次反转的原地做法
242. 有效的字母异位词	简单	只看字符多重集是否相同、不看顺序，正是本题易错点中「计数法为何不成立」的对照
214. 最短回文串	困难	同样靠拼接构造母串再求前缀函数，但要找最长回文前缀，对 KMP 的运用更深一层