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
- 转换为字符数组操作比直接字符串拼接效率更高
- 测试用例要包含k=0、k=n、k>n等特殊情况
4. 28. 实现 strStr()
4.1 算法选型分析
实现字符串查找功能，最经典的两种方案：
- 暴力匹配：时间复杂度O(m*n)
- KMP算法：时间复杂度O(m+n)，需要预处理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 模式识别技巧
判断字符串是否由重复子串构成，有两个巧妙解法：
- 双倍字符串法：s+s中去掉首尾字符后仍包含s
- KMP的next数组分析法：len % (len - next[-1]) == 0
5.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中多设置几个边界测试用例，比如空字符串、全空格字符串、k=0等情况，确保代码鲁棒性。
