1. 怎么看字符串题

字符串题表面上是在处理字符,真正考的是“顺序、区间、匹配和构造”。它和数组很像,都能用下标访问,也经常用双指针;但字符串多了一个很重要的限制:在 Python 里,str 是不可变对象。

所以刷字符串题时,我会先问四个问题:

  • 题目只是读字符,还是要频繁修改字符?
  • 题目关心的是字符顺序、单词顺序,还是子串匹配?
  • 要找的是一个固定模式,还是要判断字符频率?
  • 有没有大量重复匹配,如果有,能不能用 KMP 避免回退主串?

字符串题可以粗略分成几类:

  • 原地反转或局部反转:常用双指针。
  • 删除空格、反转单词、替换字符:常用列表收集,最后 join。
  • 判断异位词、赎金信、字母分组:本质是哈希表计数,放在哈希表模块里复习。
  • 找子串、找模式串位置、重复子串:重点是 KMP 的前缀表。
  • 连续子串满足条件:很多时候更像滑动窗口,放在数组模块里复习。

这篇主要把字符串自身最常见的处理方式和 KMP 串起来。复习时不要只记代码,要看清楚每道题到底是在维护“字符位置”“单词边界”,还是“模式串已经匹配到哪里”。

2. Python 字符串:不可变,所以构造方式很重要

Python 的字符串不能原地修改:

1
2
s = "abc"
# s[0] = "x" # TypeError

如果题目要求交换字符、反转字符,通常有两种做法:

第一种是题目直接给 list[str],比如 344. 反转字符串 给的是字符数组 s,这时可以原地交换:

1
2
3
4
5
6
7
def reverse_string(s: list[str]) -> None:
left, right = 0, len(s) - 1

while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1

这道题做的是最基础的双指针:左边一个、右边一个,每次交换后向中间靠拢。它不需要返回值,因为题目要求原地修改。容易错的地方是把 while left <= right 写进去,虽然中间元素和自己交换不影响结果,但没有必要;用 left < right 更贴近“成对交换”的含义。

第二种是题目给 str,但需要构造新字符串。这时不要在循环里频繁 ans += ch,因为字符串不可变,每次拼接都可能创建新对象。更稳的写法是先把字符放进列表,最后一次性拼接:

1
2
3
4
5
chars = []
for ch in s:
chars.append(ch)

ans = ''.join(chars)

如果需要先修改再拼回去,可以这样:

1
2
3
chars = list(s)
chars[0] = "x"
ans = ''.join(chars)

字符串切片也要注意复杂度。s[i:j] 会创建新字符串,长度为 kk 的切片就是 O(k)O(k)。如果在循环里不断切片,看起来是一层循环,实际可能变成 O(n2)O(n^2)。

3. 双指针反转:先想清楚反转范围

字符串反转类题的关键不是“会不会交换”,而是先确定每次要反转哪一段。

541. 反转字符串 II 给一个字符串 s 和整数 k,要求每隔 2k 个字符,反转前 k 个字符;如果剩余字符少于 k 个,就全部反转;如果剩余字符在 k 到 2k 之间,就只反转前 k 个。

这题看起来规则多,其实每次循环的起点都是 0, 2k, 4k...。对于每一段,真正要反转的区间是:

1
2
start = i
end = min(i + k - 1, len(chars) - 1)

代码可以直接复用双指针反转:

1
2
3
4
5
6
7
8
9
10
11
12
13
def reverse_str(s: str, k: int) -> str:
chars = list(s)

for start in range(0, len(chars), 2 * k):
left = start
right = min(start + k - 1, len(chars) - 1)

while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1

return ''.join(chars)

这里最容易错的是 right 的边界。如果直接写 start + k - 1,最后一段可能越界;如果写成 start + k,又会多反转一个字符。复习时只记一句:每 2k 一组,只反转这一组的前 k 个,所以右边界是 start + k - 1,再和数组末尾取最小。

这一类题的经验是:字符串转列表以后,思路就和数组完全一样。只要能说清楚左闭右闭区间 [left, right],交换逻辑就不会乱。

4. 单词处理:先处理空格,再处理顺序

151. 反转字符串中的单词 给一个字符串,要求反转单词顺序,并且去掉多余空格。比如:

1
"  hello   world  " -> "world hello"

这题最容易混的是:它不是把每个字符都反过来,而是把单词的顺序反过来,同时单词内部字符顺序不变。

Python 里最直接的写法是:

1
2
def reverse_words(s: str) -> str:
return ' '.join(reversed(s.split()))

split() 不传参数时,会自动按连续空白切分,并丢掉首尾空白,所以这行代码既处理了多余空格,也反转了单词顺序。

但刷题复习时还要理解手动思路,因为这能帮你看懂原地版本:

  1. 去掉多余空格,只保留单词之间一个空格。
  2. 整体反转字符串。
  3. 再把每个单词内部反转回来。

例如:

1
2
3
"hello world"
整体反转 -> "dlrow olleh"
单词内反转 -> "world hello"

如果不用 split(),可以用列表先规整空格:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def trim_spaces(s: str) -> list[str]:
chars = []
i = 0

while i < len(s):
while i < len(s) and s[i] == ' ':
i += 1

if i == len(s):
break

if chars:
chars.append(' ')

while i < len(s) and s[i] != ' ':
chars.append(s[i])
i += 1

return chars

这段代码的重点不是背,而是理解“什么时候加空格”:只有当前面已经有单词时,才在新单词前补一个空格。这样可以自然避免开头空格、结尾空格和多个连续空格。

然后可以写一个局部反转函数,把整体和单词都用同一个逻辑处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def reverse_range(chars: list[str], left: int, right: int) -> None:
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1


def reverse_words(s: str) -> str:
chars = trim_spaces(s)
reverse_range(chars, 0, len(chars) - 1)

start = 0
for i in range(len(chars) + 1):
if i == len(chars) or chars[i] == ' ':
reverse_range(chars, start, i - 1)
start = i + 1

return ''.join(chars)

这里 for i in range(len(chars) + 1) 是一个常见技巧:让 i == len(chars) 也能触发最后一个单词的处理。否则最后一个单词后面没有空格,很容易漏掉。

5. 替换和旋转:构造新串时不要反复搬家

有些字符串题不是匹配,而是按规则构造结果。比如把空格替换成 %20,或者把数字替换成指定字符串。这类题的重点是:如果字符串不可变,就不要幻想原地改,直接构造新结果。

比如“替换数字”这类题,要求把字符串中的数字字符替换成 "number":

1
2
3
4
5
6
7
8
9
10
def replace_number(s: str) -> str:
ans = []

for ch in s:
if ch.isdigit():
ans.append("number")
else:
ans.append(ch)

return ''.join(ans)

ans 里既可以放单个字符,也可以放字符串片段,最后 join 会把它们拼起来。这个写法比循环里 ans += ... 更稳,也更符合 Python 字符串不可变的特点。

旋转字符串可以用切片,也可以用三次反转。比如把字符串右旋 k 位:

1
"abcdefg", k = 2 -> "fgabcde"

切片写法很短:

1
2
3
def right_rotate(s: str, k: int) -> str:
k %= len(s)
return s[-k:] + s[:-k]

如果题目强调原地思想,可以把字符串转成列表,使用三次反转:

1
2
3
4
5
6
7
8
9
10
def right_rotate(s: str, k: int) -> str:
chars = list(s)
n = len(chars)
k %= n

reverse_range(chars, 0, n - 1)
reverse_range(chars, 0, k - 1)
reverse_range(chars, k, n - 1)

return ''.join(chars)

为什么三次反转能成立?以 abcdefg 右旋 2 位为例:

1
2
3
整体反转:gfedcba
反转前 2 个:fgedcba
反转后面:fgabcde

这类题最容易忘的是 k %= n。如果 k 大于字符串长度,不取模会导致切片范围或反转范围不好处理。取模后表示真正移动的位数。

6. KMP:匹配失败时,主串不回头

28. 找出字符串中第一个匹配项的下标 要求在主串 haystack 中找到模式串 needle 第一次出现的位置。暴力做法是从主串每个位置开始尝试匹配:

1
2
3
4
5
6
7
8
9
def str_str(haystack: str, needle: str) -> int:
if needle == "":
return 0

for i in range(len(haystack) - len(needle) + 1):
if haystack[i:i + len(needle)] == needle:
return i

return -1

这能过很多简单情况,但它的问题是匹配失败后会让主串回到下一个起点重新试。比如已经匹配了很多字符,最后一个字符失败,暴力会浪费掉前面已经知道的信息。

KMP 的核心就是:主串指针不回头,模式串指针根据前缀表回退。

假设模式串已经匹配到 j,现在 haystack[i] != needle[j]。我们不让 i 回退,而是问:模式串前面已经匹配过的这一段里,有没有一部分后缀可以当作新的前缀继续用?这就是前缀表要记录的信息。

前缀表,也常叫 lps,表示:

1
lps[i] = pattern[0:i+1] 这一段里,最长的相等前后缀长度

注意这里的前后缀都不能是整个字符串本身。比如 "abab" 的最长相等前后缀是 "ab",长度是 2。

构造 lps 时,j 表示当前已经匹配的前缀长度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def build_lps(pattern: str) -> list[int]:
lps = [0] * len(pattern)
j = 0

for i in range(1, len(pattern)):
while j > 0 and pattern[i] != pattern[j]:
j = lps[j - 1]

if pattern[i] == pattern[j]:
j += 1

lps[i] = j

return lps

这段代码最难的是 j = lps[j - 1]。它的意思不是随便把 j 减一,而是跳回“上一个可继续匹配的位置”。如果当前前后缀长度是 j,失配后,能尝试的下一个长度就是前一个字符位置记录的最长相等前后缀。

有了 lps,匹配过程也保持同一个逻辑:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def str_str(haystack: str, needle: str) -> int:
if needle == "":
return 0

lps = build_lps(needle)
j = 0

for i in range(len(haystack)):
while j > 0 and haystack[i] != needle[j]:
j = lps[j - 1]

if haystack[i] == needle[j]:
j += 1

if j == len(needle):
return i - len(needle) + 1

return -1

这里 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。

KMP 逐步演示 haystack = aabaabaaf needle = aabaaf
阶段:- 橙色 i:- 蓝色 j:- 答案:-
当前比较 -
j 的含义 -
本步结论 -
1. 构造 needle 的 lps 表
lps[i] 表示 needle[0:i+1] 的最长相等前后缀长度。
2. 用 lps 匹配 haystack
上排是主串,下排是模式串。失配时只移动下排的 needle,主串 i 不回头。

KMP 的易错点主要有三个:

  • lps 存的是长度,不是下标。
  • 失配时回退的是 j,不是 i。
  • 回退要用 while,因为回退后可能仍然失配,需要继续回退。

如果你觉得 KMP 绕,可以先记住一句话:j 代表“模式串当前匹配了多少个字符”。失败时,前缀表告诉你这几个已匹配字符里,有多少个还能继续用。

7. 重复子串:也是在看前后缀

459. 重复的子字符串 要判断一个字符串能不能由某个子串重复多次构成。比如:

1
2
3
"abab" -> True,因为 "ab" 重复 2 次
"aba" -> False
"abcabcabc" -> True,因为 "abc" 重复 3 次

这题有一个很巧的写法:

1
2
def repeated_substring_pattern(s: str) -> bool:
return s in (s + s)[1:-1]

直觉是:如果 s 是由重复子串构成的,那么把两个 s 拼起来,中间一定还能找到一个完整的 s。去掉首尾字符是为了避免直接匹配原来的那一份。

可以把它理解成一个“错位重叠”:s + s 里有两份完整的 s,一份从最左边开始,一份从中间开始。如果不去掉首尾,任何字符串都会在里面找到自己;去掉首尾以后,只有那些能由更短周期重复出来的字符串,才还能在中间重新拼出一份完整的 s。

但从 KMP 角度看,这题更能说明前缀表的意义。设 n = len(s),如果最后一个位置的 lps[-1] 是 x,说明整个字符串有长度为 x 的最长相等前后缀。若 n - x 能整除 n,就说明这个较短的周期可以重复拼出整个字符串:

1
2
3
4
5
6
def repeated_substring_pattern(s: str) -> bool:
lps = build_lps(s)
n = len(s)
longest = lps[-1]

return longest > 0 and n % (n - longest) == 0

这里 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 各自该什么时候上场就很自然了。

avatar
LittlePyx
小P的学习、研究、生活记录
Follow Me
公告
教育经历
本科:杭州电子科技大学
研究生:电子科技大学

研究方向
AI Agent 开发、计算成像、深度学习、光学

新增:代码随想录算法刷题笔记整理中,按题型与算法模板归纳。