1. 怎么看字符串题
字符串题表面上是在处理字符,真正考的是“顺序、区间、匹配和构造”。它和数组很像,都能用下标访问,也经常用双指针;但字符串多了一个很重要的限制:在 Python 里,str 是不可变对象。
所以刷字符串题时,我会先问四个问题:
- 题目只是读字符,还是要频繁修改字符?
- 题目关心的是字符顺序、单词顺序,还是子串匹配?
- 要找的是一个固定模式,还是要判断字符频率?
- 有没有大量重复匹配,如果有,能不能用 KMP 避免回退主串?
字符串题可以粗略分成几类:
- 原地反转或局部反转:常用双指针。
- 删除空格、反转单词、替换字符:常用列表收集,最后
join。 - 判断异位词、赎金信、字母分组:本质是哈希表计数,放在哈希表模块里复习。
- 找子串、找模式串位置、重复子串:重点是 KMP 的前缀表。
- 连续子串满足条件:很多时候更像滑动窗口,放在数组模块里复习。
这篇主要把字符串自身最常见的处理方式和 KMP 串起来。复习时不要只记代码,要看清楚每道题到底是在维护“字符位置”“单词边界”,还是“模式串已经匹配到哪里”。
2. Python 字符串:不可变,所以构造方式很重要
Python 的字符串不能原地修改:
1 | s = "abc" |
如果题目要求交换字符、反转字符,通常有两种做法:
第一种是题目直接给 list[str],比如 344. 反转字符串 给的是字符数组 s,这时可以原地交换:
1 | def reverse_string(s: list[str]) -> None: |
这道题做的是最基础的双指针:左边一个、右边一个,每次交换后向中间靠拢。它不需要返回值,因为题目要求原地修改。容易错的地方是把 while left <= right 写进去,虽然中间元素和自己交换不影响结果,但没有必要;用 left < right 更贴近“成对交换”的含义。
第二种是题目给 str,但需要构造新字符串。这时不要在循环里频繁 ans += ch,因为字符串不可变,每次拼接都可能创建新对象。更稳的写法是先把字符放进列表,最后一次性拼接:
1 | chars = [] |
如果需要先修改再拼回去,可以这样:
1 | chars = list(s) |
字符串切片也要注意复杂度。s[i:j] 会创建新字符串,长度为 的切片就是 。如果在循环里不断切片,看起来是一层循环,实际可能变成 。
3. 双指针反转:先想清楚反转范围
字符串反转类题的关键不是“会不会交换”,而是先确定每次要反转哪一段。
541. 反转字符串 II 给一个字符串 s 和整数 k,要求每隔 2k 个字符,反转前 k 个字符;如果剩余字符少于 k 个,就全部反转;如果剩余字符在 k 到 2k 之间,就只反转前 k 个。
这题看起来规则多,其实每次循环的起点都是 0, 2k, 4k...。对于每一段,真正要反转的区间是:
1 | start = i |
代码可以直接复用双指针反转:
1 | def reverse_str(s: str, k: int) -> str: |
这里最容易错的是 right 的边界。如果直接写 start + k - 1,最后一段可能越界;如果写成 start + k,又会多反转一个字符。复习时只记一句:每 2k 一组,只反转这一组的前 k 个,所以右边界是 start + k - 1,再和数组末尾取最小。
这一类题的经验是:字符串转列表以后,思路就和数组完全一样。只要能说清楚左闭右闭区间 [left, right],交换逻辑就不会乱。
4. 单词处理:先处理空格,再处理顺序
151. 反转字符串中的单词 给一个字符串,要求反转单词顺序,并且去掉多余空格。比如:
1 | " hello world " -> "world hello" |
这题最容易混的是:它不是把每个字符都反过来,而是把单词的顺序反过来,同时单词内部字符顺序不变。
Python 里最直接的写法是:
1 | def reverse_words(s: str) -> str: |
split() 不传参数时,会自动按连续空白切分,并丢掉首尾空白,所以这行代码既处理了多余空格,也反转了单词顺序。
但刷题复习时还要理解手动思路,因为这能帮你看懂原地版本:
- 去掉多余空格,只保留单词之间一个空格。
- 整体反转字符串。
- 再把每个单词内部反转回来。
例如:
1 | "hello world" |
如果不用 split(),可以用列表先规整空格:
1 | def trim_spaces(s: str) -> list[str]: |
这段代码的重点不是背,而是理解“什么时候加空格”:只有当前面已经有单词时,才在新单词前补一个空格。这样可以自然避免开头空格、结尾空格和多个连续空格。
然后可以写一个局部反转函数,把整体和单词都用同一个逻辑处理:
1 | def reverse_range(chars: list[str], left: int, right: int) -> None: |
这里 for i in range(len(chars) + 1) 是一个常见技巧:让 i == len(chars) 也能触发最后一个单词的处理。否则最后一个单词后面没有空格,很容易漏掉。
5. 替换和旋转:构造新串时不要反复搬家
有些字符串题不是匹配,而是按规则构造结果。比如把空格替换成 %20,或者把数字替换成指定字符串。这类题的重点是:如果字符串不可变,就不要幻想原地改,直接构造新结果。
比如“替换数字”这类题,要求把字符串中的数字字符替换成 "number":
1 | def replace_number(s: str) -> str: |
ans 里既可以放单个字符,也可以放字符串片段,最后 join 会把它们拼起来。这个写法比循环里 ans += ... 更稳,也更符合 Python 字符串不可变的特点。
旋转字符串可以用切片,也可以用三次反转。比如把字符串右旋 k 位:
1 | "abcdefg", k = 2 -> "fgabcde" |
切片写法很短:
1 | def right_rotate(s: str, k: int) -> str: |
如果题目强调原地思想,可以把字符串转成列表,使用三次反转:
1 | def right_rotate(s: str, k: int) -> str: |
为什么三次反转能成立?以 abcdefg 右旋 2 位为例:
1 | 整体反转:gfedcba |
这类题最容易忘的是 k %= n。如果 k 大于字符串长度,不取模会导致切片范围或反转范围不好处理。取模后表示真正移动的位数。
6. KMP:匹配失败时,主串不回头
28. 找出字符串中第一个匹配项的下标 要求在主串 haystack 中找到模式串 needle 第一次出现的位置。暴力做法是从主串每个位置开始尝试匹配:
1 | def str_str(haystack: str, needle: str) -> int: |
这能过很多简单情况,但它的问题是匹配失败后会让主串回到下一个起点重新试。比如已经匹配了很多字符,最后一个字符失败,暴力会浪费掉前面已经知道的信息。
KMP 的核心就是:主串指针不回头,模式串指针根据前缀表回退。
假设模式串已经匹配到 j,现在 haystack[i] != needle[j]。我们不让 i 回退,而是问:模式串前面已经匹配过的这一段里,有没有一部分后缀可以当作新的前缀继续用?这就是前缀表要记录的信息。
前缀表,也常叫 lps,表示:
1 | lps[i] = pattern[0:i+1] 这一段里,最长的相等前后缀长度 |
注意这里的前后缀都不能是整个字符串本身。比如 "abab" 的最长相等前后缀是 "ab",长度是 2。
构造 lps 时,j 表示当前已经匹配的前缀长度:
1 | def build_lps(pattern: str) -> list[int]: |
这段代码最难的是 j = lps[j - 1]。它的意思不是随便把 j 减一,而是跳回“上一个可继续匹配的位置”。如果当前前后缀长度是 j,失配后,能尝试的下一个长度就是前一个字符位置记录的最长相等前后缀。
有了 lps,匹配过程也保持同一个逻辑:
1 | def str_str(haystack: str, needle: str) -> int: |
这里 i 一直向右走,从不回退。失配时只调整 j,也就是模式串已经匹配到的位置。匹配成功时 j += 1;当 j == len(needle),说明整个模式串都匹配完了,起点就是 i - len(needle) + 1。
看 lps 时,不要先把它当成一串数字背。先抓住一个含义:j 表示“当前已经能复用的前缀长度”。因为下标从 0 开始,所以当 j = 2 时,意思是前面已经有长度为 2 的前缀可以复用,下一步要拿 needle[i] 去和 needle[2] 比较。
如果 needle[i] == needle[j],说明这个可复用前缀还能再延长一位,于是 j += 1,并且 lps[i] = j。如果不相等,就不能直接把 j 减 1,而是跳到更短、但仍然可能成立的前缀长度,也就是 j = lps[j - 1]。
下面用 haystack = "aabaabaaf"、needle = "aabaaf" 演示一次完整过程。先看 lps 怎么生成,再看真正匹配时 i = 5 失配以后,主串指针 i 留在原地,模式串指针 j 从 5 回退到 lps[4] = 2。
lps[i] 表示 needle[0:i+1] 的最长相等前后缀长度。needle,主串 i 不回头。KMP 的易错点主要有三个:
lps存的是长度,不是下标。- 失配时回退的是
j,不是i。 - 回退要用
while,因为回退后可能仍然失配,需要继续回退。
如果你觉得 KMP 绕,可以先记住一句话:j 代表“模式串当前匹配了多少个字符”。失败时,前缀表告诉你这几个已匹配字符里,有多少个还能继续用。
7. 重复子串:也是在看前后缀
459. 重复的子字符串 要判断一个字符串能不能由某个子串重复多次构成。比如:
1 | "abab" -> True,因为 "ab" 重复 2 次 |
这题有一个很巧的写法:
1 | def repeated_substring_pattern(s: str) -> bool: |
直觉是:如果 s 是由重复子串构成的,那么把两个 s 拼起来,中间一定还能找到一个完整的 s。去掉首尾字符是为了避免直接匹配原来的那一份。
可以把它理解成一个“错位重叠”:s + s 里有两份完整的 s,一份从最左边开始,一份从中间开始。如果不去掉首尾,任何字符串都会在里面找到自己;去掉首尾以后,只有那些能由更短周期重复出来的字符串,才还能在中间重新拼出一份完整的 s。
但从 KMP 角度看,这题更能说明前缀表的意义。设 n = len(s),如果最后一个位置的 lps[-1] 是 x,说明整个字符串有长度为 x 的最长相等前后缀。若 n - x 能整除 n,就说明这个较短的周期可以重复拼出整个字符串:
1 | def repeated_substring_pattern(s: str) -> bool: |
这里 n - longest 可以理解成最小重复单元的候选长度。比如 "ababab" 的 longest = 4,n - longest = 2,对应重复单元 "ab"。因为 6 % 2 == 0,所以可以整除。
这题容易错在只判断 longest > 0。有相等前后缀不一定代表能完整重复,还必须满足周期长度能整除总长度。比如有些字符串开头和结尾相似,但中间不能被同一个周期铺满。
8. 复习总览
- Python 字符串不可变,频繁修改时先转
list,最后''.join(...)。 - 原地反转类题,本质是双指针交换,先确定
[left, right]的范围。 - 541. 反转字符串 II:每
2k一组,只反转前k个,右边界是min(start + k - 1, n - 1)。 - 151. 反转字符串中的单词:先处理多余空格,再反转单词顺序;Python 可用
' '.join(reversed(s.split()))。 - 构造新字符串时,优先用列表收集片段,不要在大循环里反复
+=。 - 右旋字符串:记得
k %= n;切片很短,三次反转更体现原地思想。 - KMP 的核心是主串
i不回退,模式串j按lps回退。 lps[i]表示pattern[0:i+1]的最长相等前后缀长度。- KMP 失配时写
while j > 0 and text[i] != pattern[j]: j = lps[j - 1]。 - 重复子串可以用
(s + s)[1:-1],也可以用 KMP 判断n % (n - lps[-1]) == 0。
字符串题复习时最重要的是别把所有题都混成“遍历字符”。先判断它是在修改字符、整理单词、构造新串,还是做模式匹配。问题类型一清楚,双指针、列表构造、哈希表、KMP 各自该什么时候上场就很自然了。





