我的 LeetCode 日记：Day 9 - 字符串终章与 KMP 算法

今天，我迎来了字符串章节的收官之日。如果说昨天的内容是基础操作的热身，那么今天就是一场真刀真枪的算法硬仗。我不仅要综合运用之前学到的技巧来解决复杂的单词翻转问题，还要正面迎战字符串算法中一座绕不开的高峰——KMP 算法。

今天的学习强度很大，尤其是 KMP 算法，正如 Carl 哥所说，需要“硬啃”。但啃下来之后，那种豁然开朗的感觉，是前所未有的。

一、实战演练：从宏观操作到微观匹配

1. LeetCode 151. 翻转字符串里的单词

题目描述: 给你一个字符串 s ，请你反转字符串中 单词 的顺序。单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。返回一个由单个空格分隔的单词字符串，不包含 任何前导或尾随空格。

• 学习感悟: 这道题是字符串综合操作的“期末考试”。一个看似简单的需求，却需要处理去除多余空格、翻转整体、再翻转局部等多个步骤，非常考验代码的鲁棒性。
  • Pythonic 解法: 一行 " ".join(s.split()[::-1]) 就能搞定，split() 自动处理了各种空格情况，非常优雅。
  • 手动实现: 为了真正锻炼能力，我用 deque (双端队列) 手动实现了一遍。我先清理掉首尾的空格，然后在字符串中识别出每个单词，并用 appendleft 将它们依次插入 deque 的头部。这样做能巧妙地实现单词顺序的反转。这个过程让我对处理字符串中的边界和状态变化有了更深的理解。
• 资源包 (题目/文章/视频): 代码随想录-151.翻转字符串里的单词

我的实现 1：Pythonic 一行解

class Solution:def reverseWords(self, s: str) -> str:# split() 会自动处理多个空格，并返回一个单词列表# [::-1] 对列表进行反转# " ".join() 用单个空格将单词连接起来return " ".join(s.split()[::-1])

我的实现 2：手动双端队列法

from collections import dequeclass Solution:def reverseWords(self, s: str) -> str:left, right = 0, len(s) - 1# 1. 去除首尾空格while left <= right and s[left] == ' ': left += 1while left <= right and s[right] == ' ': right -= 1d = deque()word = []# 2. 遍历并识别单词while left <= right:if s[left] != ' ':word.append(s[left])elif word: # 遇到空格，且 word 列表不为空d.appendleft("".join(word))word = []left += 1d.appendleft("".join(word)) # 加入最后一个单词return " ".join(d)

2. 卡码网：55. 右旋转字符串

题目描述: 给定一个字符串 S 和一个数字 K，请将 S 向右循环移动 K 位。

• 学习感悟: 这道题有一个非常巧妙的解法。向右旋转 k 位，本质上就是把字符串的最后 k 个字符，移动到字符串的最前面。在 Python 中，利用字符串切片可以轻松实现。s[n-k:] 就是最后 k 个字符，s[:n-k] 是前面剩下的部分，拼接起来即可。我还注意到了 k 可能大于字符串长度 n，所以用 k %= n 来处理，非常严谨。
• 资源包 (题目/文章): 代码随想录-卡码网-55.右旋转字符串

我的实现：字符串切片

# 假设在卡码网环境下
k = int(input())
s = input()
n = len(s)if n == 0 or k <= 0:print(s)
else:k %= n # 处理 k > n 的情况# 将后 k 个字符与前 n-k 个字符拼接rotated_s = s[n-k:] + s[:n-k]print(rotated_s)

3. LeetCode 28. 实现 strStr() (KMP 算法)

题目描述: 实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1。

• 学习感悟: 终于，我迎战了传说中的 KMP 算法。暴力解法很简单，但 KMP 的精髓在于避免主串指针 i 的回溯。它通过预处理 needle 字符串，构建一个 next 数组，来记录模式串的“最长相等前后缀”。当匹配发生失配时，next 数组会告诉我们 needle 应该“滑动”到哪个位置，而不是傻傻地从头再来。

  • 构建 next 数组：这是 KMP 最难理解的部分。它本身就是一个“模式串自我匹配”的过程。通过 i 和 j 两个指针在模式串上移动，不断求解并记录每个子串的最长相等前后缀长度。
    

  • 匹配过程：利用 next 数组，当 haystack[i] 和 needle[j] 不匹配时，j 会根据 next[j-1] 的值进行“回退”，而 i 始终勇往直前。
    我反复观看了视频，在纸上画图推演，才最终理解了指针 j 的跳动逻辑。这确实需要硬啃！

• 资源包 (题目/文章/视频): 代码随想录-28.实现strStr()

我的实现：KMP 算法

class Solution:def strStr(self, haystack: str, needle: str) -> int:n, m = len(haystack), len(needle)if m == 0: return 0# 1. 计算 next 数组next_arr = self._compute_next(needle)j = 0 # 指向 needle# 2. 主串匹配for i in range(n): # i 指向 haystack# 不匹配时，根据 next 数组回退 jwhile j > 0 and haystack[i] != needle[j]:j = next_arr[j - 1]# 匹配时，j 后移if haystack[i] == needle[j]:j += 1# needle 完全匹配if j == m:return i - m + 1return -1def _compute_next(self, pattern: str) -> list:m = len(pattern)next_arr = [0] * mj = 0 # 前缀末尾for i in range(1, m): # i 后缀末尾while j > 0 and pattern[i] != pattern[j]:j = next_arr[j - 1]if pattern[i] == pattern[j]:j += 1next_arr[i] = jreturn next_arr

4. LeetCode 459. 重复的子字符串

题目描述: 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。

• 学习感悟: 这是 KMP 算法一个出神入化的应用。一个字符串如果可以由子串重复构成，那么它的 next 数组会揭示这个秘密。
  • 核心公式: 如果一个字符串 s 的长度为 n，其 next 数组的最后一位是 next[-1]，那么 k = n - next[-1] 就是最小重复子串的长度（如果存在的话）。
  • 判断条件: 如果 next[-1] 大于 0（说明有相等的前后缀），并且 n 能够被 k 整除，那么这个字符串就是由重复子串构成的。这个结论的推导过程非常巧妙，让我再次感叹数学与算法的完美结合。
• 资源包 (题目/文章/视频): 代码随想录-459.重复的子字符串

我的实现：KMP next 数组应用

class Solution:# _compute_next 方法与上一题相同def _compute_next(self, pattern: str) -> list:# ... (same as above)m = len(pattern)next_arr = [0] * mj = 0for i in range(1, m):while j > 0 and pattern[i] != pattern[j]:j = next_arr[j - 1]if pattern[i] == pattern[j]:j += 1next_arr[i] = jreturn next_arrdef repeatedSubstringPattern(self, s: str) -> bool:n = len(s)if n == 0: return Falsenext_arr = self._compute_next(s)last_next_val = next_arr[-1]# 如果 next 数组最后一位 > 0，说明存在最长相等前后缀if last_next_val > 0:# 计算最小重复单元的长度repeat_len = n - last_next_val# 如果总长度是重复单元长度的整数倍if n % repeat_len == 0:return Truereturn False

三、总结与回顾

1. 字符串总结

字符串章节的学习到此结束。从基础的双指针操作，到复杂的 KMP 算法，我掌握了一套完整的字符串处理工具链。核心在于指针的灵活运用和对特定算法（如KMP）原理的深刻理解。

• 文章链接: 代码随想录-字符串总结

2. 双指针回顾

双指针思想贯穿了数组、链表、字符串等多个章节，是优化时间复杂度的利器。无论是快慢指针（判断环、找倒数第k个节点），还是左右指针（反转、二分查找、N数之和），其思想都是通过两个指针的协同移动，将 O(n²) 的问题降维到 O(n)。这次回顾让我把分散在各章节的知识点串联了起来，形成了更系统的认识。

• 文章链接: 代码随想录-双指针总结

收官感言

字符串章节的学习，特别是 KMP 算法，是一次智力上的巨大挑战和享受。我不仅学会了算法本身，更体会到了算法设计中蕴含的数学之美。带着这份收获，我将充满信心地迎接下一个章节的挑战！