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 #34;abcde#34;, goal #34;cdeab#34;输出true解释原字符串经过2次旋转后刚好匹配目标字符串示例 2输入s #34;abcde#34;, goal #34;abced#34;输出false解释无论旋转多少次原字符串都无法匹配目标字符串1.2 题目提示1 \lt; s\.length, goal\.length \lt; 100s和goal仅由小写英文字母组成二、解题前置思路分析在解题前首先可以确定一个核心前置条件如果两个字符串长度不相等一定无法通过旋转互相转换直接返回false。这是所有解法的通用剪枝逻辑能快速过滤无效用例。当且仅当len\(s\) len\(goal\)时才需要进一步判断是否可以通过旋转匹配。本文提供三种梯度解法从暴力模拟到进阶算法层层优化适配不同刷题阶段的学习需求解法一暴力模拟旋转直观易懂入门首选解法二字符串拼接匹配巧用特性极简代码解法三KMP字符串匹配算法进阶优化最优时间复杂度三、解法一暴力模拟旋转法3.1 解题思路根据题目旋转定义直接模拟每一次旋转操作首先判断两字符串长度是否一致不一致直接返回false字符串长度为n时最多只需旋转n\-1次旋转n次后回到原字符串每次旋转将首字符移至末尾生成新字符串每次旋转后对比是否等于目标字符串匹配成功返回true全部旋转完毕未匹配返回false3.2 完整代码实现classSolution:defrotateString(self,s:str,goal:str)-bool:# 长度不同直接返回Falseiflen(s)!len(goal):returnFalsenlen(s)# 最多旋转n-1次for_inrange(n):# 每次旋转首字符移到末尾ifsgoal:returnTruess[1:]s[0]# 所有旋转情况均不匹配returnFalse3.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 #34;abcde#34;ss #34;abcdeabcde#34;s的所有旋转结果bcdea、cdeab、deabc、eabcd均是 ss 的子串。因此解题逻辑可简化为长度相等 且 goal 是 ss 的子串即返回true。4.2 完整代码实现classSolution:defrotateString(self,s:str,goal:str)-bool:# 长度一致且goal是ss的子串即为合法旋转结果returnlen(s)len(goal)andgoalinss4.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)。整体逻辑不变先判断字符串长度是否相等以s\s为文本串goal为模式串通过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):nlen(pattern)next_arr[0]*n j0foriinrange(1,n):# 回退逻辑whilej0andpattern[i]!pattern[j]:jnext_arr[j-1]ifpattern[i]pattern[j]:j1next_arr[i]jelse:next_arr[i]0returnnext_arr# KMP匹配函数defkmp_search(text,pattern,next_arr):m,nlen(text),len(pattern)j0foriinrange(m):whilej0andtext[i]!pattern[j]:jnext_arr[j-1]iftext[i]pattern[j]:j1# 匹配完成ifjn:returnTruereturnFalse# 拼接文本串生成next数组执行匹配textss next_arrget_next(goal)returnkmp_search(text,goal,next_arr)5.4 代码详解get_next函数预处理模式串goal生成最长相等前后缀数组记录每个位置的最优回退位置kmp_search函数遍历文本串ss结合next数组进行高效匹配无重复遍历匹配成功立即返回True遍历结束未匹配返回False5.5 复杂度分析时间复杂度O(n)构建next数组耗时O(n)KMP匹配耗时O(2n)整体为线性复杂度空间复杂度O(n)需要额外存储next数组与拼接后的文本串六、三种解法对比总结解法优点缺点适用场景时间复杂度暴力模拟法逻辑直观、极易理解、适合入门效率较低存在重复操作新手刷题、理解旋转逻辑O(n²)字符串拼接法代码极简、秒杀题目、书写最快底层仍为暴力匹配大数据量效率一般日常刷题、面试快速解题O(n²)KMP算法时间复杂度最优适配大数据量代码量大、逻辑较复杂算法进阶、面试手撕算法、大数据场景O(n)七、面试核心考点总结基础考点字符串旋转的特性s\s包含所有旋转子串是本题解题核心优化考点暴力解法的时间复杂度瓶颈KMP算法优化思路边界考点必须先判断字符串长度是否相等否则会出现错误匹配手撕考点面试中常要求手写KMP算法避免调用内置API