字符串操作与算法面试实战：翻转、旋转与KMP解析

1. 字符串操作实战算法训练营第九天精要今天要啃的这四道字符串题目可以说是算法面试中的常客了。151翻转字符串单词、55右旋转字符串、28实现strStr()以及459重复子字符串覆盖了字符串处理中最核心的几种操作模式。作为经历过数十场算法面试的老兵我发现这些题目看似基础但实际编码时处处是坑。下面我就结合自己的踩坑经验带大家逐个击破。2. 151. 翻转字符串里的单词2.1 问题本质剖析这道题要求翻转字符串中单词的顺序但保持单词内部字符顺序不变。例如the sky is blue变成blue is sky the。看似简单但实际处理时需要同时考虑前导/后缀空格处理单词间多余空格压缩整体翻转与局部翻转的配合2.2 最优解法步骤拆解预处理去空格使用双指针法去除多余空格时间复杂度O(n)def trim_spaces(s): left, right 0, len(s) - 1 # 去掉前后空格 while left right and s[left] : left 1 while left right and s[right] : right - 1 # 去掉中间多余空格 output [] while left right: if s[left] ! : output.append(s[left]) elif output[-1] ! : # 确保单词间只保留一个空格 output.append(s[left]) left 1 return output整体翻转单词局部翻转def reverse_words(s): # 先处理空格 chars trim_spaces(s) # 翻转整个字符数组 reverse(chars, 0, len(chars) - 1) # 翻转每个单词 start 0 for end in range(len(chars)): if end len(chars) - 1 or chars[end 1] : reverse(chars, start, end) start end 2 return .join(chars) def reverse(arr, left, right): while left right: arr[left], arr[right] arr[right], arr[left] left 1 right - 12.3 易错点警示注意直接使用语言内置的split()reverse()组合虽然简洁但在面试中通常会被要求手写底层逻辑。此外处理空格时容易遗漏连续多个空格的情况。3. 卡码网55.右旋转字符串3.1 问题变形思考题目要求将字符串右旋转k位例如abcdefg右旋2位得到fgabcde。这类旋转问题有个通用技巧整体翻转前部翻转后部翻转3.2 具体实现方案def right_rotate(s, k): n len(s) k % n # 处理k大于长度的情况 arr list(s) # 整体翻转 reverse(arr, 0, n - 1) # 翻转前k个 reverse(arr, 0, k - 1) # 翻转剩余部分 reverse(arr, k, n - 1) return .join(arr)3.3 边界处理要点当k大于字符串长度时实际有效旋转次数是k%n转换为字符数组操作比直接字符串拼接效率更高测试用例要包含k0、kn、kn等特殊情况4. 28. 实现 strStr()4.1 算法选型分析实现字符串查找功能最经典的两种方案暴力匹配时间复杂度O(m*n)KMP算法时间复杂度O(mn)需要预处理next数组4.2 KMP算法完整实现def strStr(haystack, needle): if not needle: return 0 # 构建next数组 next_arr get_next(needle) i j 0 while i len(haystack) and j len(needle): if j -1 or haystack[i] needle[j]: i 1 j 1 else: j next_arr[j] return i - j if j len(needle) else -1 def get_next(pattern): next_arr [-1] * len(pattern) i, j 0, -1 while i len(pattern) - 1: if j -1 or pattern[i] pattern[j]: i 1 j 1 next_arr[i] j else: j next_arr[j] return next_arr4.3 调试经验分享关键理解next数组的含义——记录模式串中前缀和后缀的最长公共元素长度。调试时建议先用小样例手工计算next数组再与程序输出对比。5. 459.重复的子字符串5.1 模式识别技巧判断字符串是否由重复子串构成有两个巧妙解法双倍字符串法ss中去掉首尾字符后仍包含sKMP的next数组分析法len % (len - next[-1]) 05.2 最优解法实现def repeatedSubstringPattern(s): n len(s) next_arr get_next(s) return next_arr[-1] ! -1 and n % (n - next_arr[-1] - 1) 05.3 数学原理说明假设字符串由m个重复子串构成则字符串周期为n/m。通过next数组可以找到这个周期关系next数组最后一位表示整个字符串的最长相同前后缀n - next[-1] - 1就是最小重复单元长度6. 综合训练建议按顺序练习这四道题先自己尝试实现再对照标准解法每道题至少手写3遍直到能无提示完整写出重点掌握KMP算法的next数组构建过程记录每种解法的时间/空间复杂度我在实际面试中发现字符串类题目最考验代码的严谨性。建议大家在本地IDE中多设置几个边界测试用例比如空字符串、全空格字符串、k0等情况确保代码鲁棒性。