LeetCode 796.旋转字符串 详细题解（三种解法+代码实战）

LeetCode 796.旋转字符串 详细题解（三种解法+代码实战）

一、题目描述

给定两个字符串s和goal。如果在若干次旋转操作之后，s能变成goal，那么返回true，否则返回false。

旋转操作定义：将字符串s最左侧的字符移动到字符串最右侧。

示例：s = \&\#34;abcde\&\#34;，旋转1次结果为\&\#34;bcdea\&\#34;，旋转2次结果为\&\#34;cdeab\&\#34;。

1.1 示例展示

• 示例 1

• 输入：s = "abcde", goal = "cdeab"

• 输出：true

• 解释：原字符串经过2次旋转后，刚好匹配目标字符串

• 示例 2

• 输入：s = "abcde", goal = "abced"

• 输出：false

• 解释：无论旋转多少次，原字符串都无法匹配目标字符串

1.2 题目提示

• 1 \<= s\.length, goal\.length \<= 100

• s和goal仅由小写英文字母组成

二、解题前置思路分析

在解题前，首先可以确定一个核心前置条件：如果两个字符串长度不相等，一定无法通过旋转互相转换，直接返回false。这是所有解法的通用剪枝逻辑，能快速过滤无效用例。

当且仅当len\(s\) == len\(goal\)时，才需要进一步判断是否可以通过旋转匹配。

本文提供三种梯度解法，从暴力模拟到进阶算法，层层优化，适配不同刷题阶段的学习需求：

1. 解法一：暴力模拟旋转（直观易懂，入门首选）

2. 解法二：字符串拼接匹配（巧用特性，极简代码）

3. 解法三：KMP字符串匹配算法（进阶优化，最优时间复杂度）

三、解法一：暴力模拟旋转法

3.1 解题思路

根据题目旋转定义，直接模拟每一次旋转操作：

1. 首先判断两字符串长度是否一致，不一致直接返回false

2. 字符串长度为n时，最多只需旋转n\-1次（旋转n次后回到原字符串）

3. 每次旋转：将首字符移至末尾，生成新字符串

4. 每次旋转后对比是否等于目标字符串，匹配成功返回true，全部旋转完毕未匹配返回false

3.2 完整代码实现

classSolution:defrotateString(self,s:str,goal:str)->bool:# 长度不同直接返回Falseiflen(s)!=len(goal):returnFalsen=len(s)# 最多旋转n-1次for_inrange(n):# 每次旋转：首字符移到末尾ifs==goal:returnTrues=s[1:]+s[0]# 所有旋转情况均不匹配returnFalse

3.3 代码详解

• len\(s\) \!= len\(goal\)：前置剪枝，快速排除无效场景

• 循环次数为字符串长度n：覆盖所有旋转可能性（包含原字符串本身）

• s\[1:\] \+ s\[0\]：Python字符串切片实现旋转，简洁高效，截取除首字符外的所有字符，拼接首字符到末尾

• 每次旋转后即时匹配，匹配成功立即返回，减少无效循环

3.4 复杂度分析

• 时间复杂度：O(n²)，n为字符串长度。最多循环n次，每次切片拼接操作耗时O(n)

• 空间复杂度：O(n)，每次旋转会生成新的字符串，占用n大小的空间

四、解法二：字符串拼接特性法（最优简洁解法）

4.1 核心解题特性

这是本题的核心技巧：字符串 s 的所有旋转结果，全部包含在 s + s 的拼接字符串中。

举例验证：s = "abcde"，s+s = "abcdeabcde"

s的所有旋转结果：bcdea、cdeab、deabc、eabcd，均是 s+s 的子串。

因此解题逻辑可简化为：长度相等 且 goal 是 s+s 的子串，即返回true。

4.2 完整代码实现

classSolution:defrotateString(self,s:str,goal:str)->bool:# 长度一致且goal是s+s的子串，即为合法旋转结果returnlen(s)==len(goal)andgoalins+s

4.3 代码详解

• 第一步判断长度相等：规避长度不同的错误场景

• goal in s \+ s：利用Python内置子串匹配，直接判断目标字符串是否为旋转结果

• 代码极简，一行核心逻辑，是刷题最优解，效率高、易记忆

4.4 复杂度分析

• 时间复杂度：O(n²)，Python内置in操作底层为暴力匹配，最坏情况遍历n长度字符串，匹配耗时O(n)

• 空间复杂度：O(n)，需要创建长度为2n的拼接字符串

五、解法三：KMP算法（进阶最优时间复杂度）

5.1 解题思路

解法二的内置子串匹配最坏时间复杂度为O(n²)，我们可以手动实现KMP字符串匹配算法，将时间复杂度优化到O(n)。

整体逻辑不变：

1. 先判断字符串长度是否相等

2. 以s\+s为文本串，goal为模式串

3. 通过KMP算法高效匹配子串，判断是否存在匹配结果

5.2 KMP算法原理简述

KMP算法通过预处理模式串，生成最长相等前后缀数组（next数组），匹配失败时无需回退文本串指针，仅回退模式串指针，避免重复匹配，将时间复杂度从O(n²)优化至O(n)。

5.3 完整代码实现

classSolution:defrotateString(self,s:str,goal:str)->bool:# 前置判断：长度不同直接返回Falseiflen(s)!=len(goal):returnFalseiflen(s)==0:returnTrue# 构建next数组（KMP核心）defget_next(pattern):n=len(pattern)next_arr=[0]*n j=0foriinrange(1,n):# 回退逻辑whilej>0andpattern[i]!=pattern[j]:j=next_arr[j-1]ifpattern[i]==pattern[j]:j+=1next_arr[i]=jelse:next_arr[i]=0returnnext_arr# KMP匹配函数defkmp_search(text,pattern,next_arr):m,n=len(text),len(pattern)j=0foriinrange(m):whilej>0andtext[i]!=pattern[j]:j=next_arr[j-1]iftext[i]==pattern[j]:j+=1# 匹配完成ifj==n:returnTruereturnFalse# 拼接文本串，生成next数组，执行匹配text=s+s next_arr=get_next(goal)returnkmp_search(text,goal,next_arr)

5.4 代码详解

• get_next函数：预处理模式串goal，生成最长相等前后缀数组，记录每个位置的最优回退位置

• kmp_search函数：遍历文本串s+s，结合next数组进行高效匹配，无重复遍历

• 匹配成功立即返回True，遍历结束未匹配返回False

5.5 复杂度分析

• 时间复杂度：O(n)，构建next数组耗时O(n)，KMP匹配耗时O(2n)，整体为线性复杂度

• 空间复杂度：O(n)，需要额外存储next数组与拼接后的文本串

六、三种解法对比总结

解法	优点	缺点	适用场景	时间复杂度
暴力模拟法	逻辑直观、极易理解、适合入门	效率较低，存在重复操作	新手刷题、理解旋转逻辑	O(n²)
字符串拼接法	代码极简、秒杀题目、书写最快	底层仍为暴力匹配，大数据量效率一般	日常刷题、面试快速解题	O(n²)
KMP算法	时间复杂度最优，适配大数据量	代码量大、逻辑较复杂	算法进阶、面试手撕算法、大数据场景	O(n)

七、面试核心考点总结

1. 基础考点：字符串旋转的特性，s\+s包含所有旋转子串，是本题解题核心

2. 优化考点：暴力解法的时间复杂度瓶颈，KMP算法优化思路

3. 边界考点：必须先判断字符串长度是否相等，否则会出现错误匹配

4. 手撕考点：面试中常要求手写KMP算法，避免调用内置API