✍️ 01-数据结构与算法 · 主题 13:字符串(收尾篇)¶
字符串题四大类:反转、匹配、回文、计数——模板集中,性价比极高。 本 notebook 目标:背熟双指针/哈希计数/KMP 概念 → 吃透 9 道高频题 → 通过 25 道自测。
前置:主题 2(双指针)、主题 12(位运算)。运行环境:Python 3.8+。
核心概念¶
(a) 🗂️ 字符串四大类:反转、匹配、回文、计数¶
字符串题四大类:反转、匹配、回文、计数——模板集中、性价比极高。本 notebook 背熟双指针/哈希计数/KMP 概念,吃透 9 道高频题,收尾 13 个主题系列。
flowchart TB
N1["✍️ 字符串题四大类总览"] --> N2["反转类:344 / 151"]
N1 --> N3["匹配类:28 暴力 + KMP 概念"]
N1 --> N4["回文类:125 / 680"]
N1 --> N5["计数哈希类:242 / 49 / 387"]
N2 --> N6["字符串转换:8 atoi"]
N3 --> N7["补充:Rabin-Karp 滚动哈希"]
N4 --> N8["常见 bug 与边界"]
N7 --> N8
N8 --> N9["自测清单与结课寄语"]
- N1 · 四大类总览:字符串题看起来五花八门,其实只有四大类:反转/变换、匹配、回文、计数。题目先归类再套模板,性价比极高。
- N2 · 反转类:344 原地反转字符串用双指针左右交换;151 反转单词顺序用 split 逆序,或"先整体反转再逐词反转"。
- N3 · 匹配类:28 题先会暴力(逐位尝试),再理解 KMP 的核心——主串不回退、用 next 数组跳过已匹配的前缀,一句话讲清原理即可,面试再深入展开。
- N4 · 回文类:125 验证回文串用双指针 + 忽略大小写和符号;680 允许删一个字符,左右各试删一次即可。
- N5 · 计数哈希类:242 异位词用 26 长度数组计数;49 分组用"排序后的串"或"计数元组"当 key;387 第一个唯一字符扫两遍。
- N6 · 字符串转换 atoi:考的是工程细节:跳过空格、处理正负号、溢出截断、非法字符终止——边界条件越多越要一条条列清楚。
- N7 · Rabin-Karp 滚动哈希:补充内容:把"子串相等"变成"哈希相等",O(n) 匹配 + 哈希碰撞处理,是 KMP 之外的另一种匹配思路。
- N8 · 常见 bug 与边界:Python 字符串不可变(要转 list 才能原地改)、回文判断的奇偶长度、atoi 的 32 位溢出边界。
- N9 · 自测清单与结课寄语:L1/L2/L3 自测收尾:13 个主题全部完成,字符串题记住"先归类再下手",系列结课。
§1 字符串题四大类总览¶
| 类 | 代表题 | 核心工具 |
|---|---|---|
| 反转/变换 | 344 / 151 / 541 | 双指针、split、切片 |
| 匹配 | 28 / 459 | 朴素 / KMP / Rabin-Karp |
| 回文 | 125 / 680 / 5 | 双指针向中间、中心扩展 |
| 计数/哈希 | 242 / 49 / 387 | 计数器、排序键、ASCII 数组 |
Python 字符串特点(常被问):
- 不可变:
s[i] = 'x'会报错,必须构造新字符串或转 list - 拼接
+在循环中产生新对象 $O(n^2)$——用''.join(list)或list收集 s[::-1]反转、s.split()按空白切、s.split(',')指定分隔符
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# ============== 344 反转字符串 / 151 反转单词(split 版) ==============
# 【题目目标】① 344:原地反转字符列表,用双指针从两端向中间交换;② 151:把
# 字符串中单词的顺序反转(split 直观版)
# 【算法思路】344:左指针 l、右指针 r 从两端向中间交换字符,相遇即完成;151:
# s.split() 默认按任意空白切分并自动去掉空串 → [::-1] 反转单词顺序 →
# 用单个空格 ' '.join 拼接
# 【变量含义】s:字符列表(344)或原字符串(151);l/r:左右指针;
# split()[::-1]:拆出的单词列表反转
# 【循环不变量】l 左侧与 r 右侧的字符均已完成交换,未处理区间为 [l, r]
# 【递归终止】无递归;while l < r 两指针相遇即结束
# 【关键边界】344 的入参必须是 list(字符串不可变,s[i]=... 会报错);151 的
# split() 不能带分隔符参数(不带参数才能吃掉连续空格)
# 【复杂度】344:O(n) 时间、O(1) 空间;151:O(n) 时间、O(n) 空间(split/join)
# 344. 反转字符串:原地反转字符列表,用双指针从两端向中间交换
def reverse_string(s):
# 原地反转字符列表
l, r = 0, len(s) - 1 # 左、右指针分别指向两端
while l < r: # 两指针未相遇就继续
s[l], s[r] = s[r], s[l] # 交换左右两个字符
l += 1 # 左指针右移
r -= 1 # 右指针左移
return s # 返回反转后的列表
# 151. 反转字符串中的单词:拆出所有单词 → 反转顺序 → 用单个空格拼接
def reverse_words(s):
# split 默认按任意空白切且去掉空串
return ' '.join(s.split()[::-1]) # split 拆词、[::-1] 反转顺序、空格 join
print('344:', reverse_string(list('hello'))) # ['o','l','l','e','h']
print('344:', reverse_string(list('a'))) # ['a']
print('151:', reverse_words('the sky is blue')) # 'blue is sky the'
print('151:', reverse_words(' hello world ')) # 'world hello'
print('151:', reverse_words('a good example')) # 'example good a'
344: ['o', 'l', 'l', 'e', 'h'] 344: ['a'] 151: blue is sky the 151: world hello 151: example good a
§3 字符串匹配:28 找出字符串中第一个匹配项的下标¶
朴素匹配:
$$\text{匹配失败就 } i \gets i+1,\ j \gets 0 \quad \Rightarrow \quad O(n \cdot m)$$
KMP 核心思想:匹配失败时不回退主串指针,利用「前缀函数」跳到已匹配的前缀:
$$next[j] = \max\{ k < j : \text{模式串前 } k \text{ 个字符} = \text{后 } k \text{ 个字符} \}$$
复杂度:$O(n + m)$。
Rabin-Karp(滚动哈希)概念:
$$\text{hash}(s) = \sum s_i \cdot base^i \bmod p$$
窗口滑动时 $O(1)$ 更新哈希,冲突时再逐位验证。
💡 面试答「KMP 让主串不回退,复杂度 O(n+m)」即可;能写出 next 数组是加分。
# ============== 28 字符串匹配:朴素版 + KMP 版 ==============
# 【题目目标】找出模式串 needle 在主串 haystack 中第一次出现的下标,找不到返回 -1
# 【算法思路】朴素版:枚举每个可能的起点 i(0..n-m),切片比较是否等于 needle,
# O(n·m);KMP 版:匹配失败时主串指针不回退,利用 next 数组(模式串各
# 前缀的最长相等前后缀长度)跳过已匹配的部分,主串指针只前进,总复杂度
# O(n+m)
# 【变量含义】haystack/needle:主串与模式串;n/m:长度;i:匹配起点/主串指针;
# j:当前已匹配的前缀长度;nxt:next 数组(nxt[i] = 前 i+1 个字符的最长
# 相等前后缀长度);nxt[j-1]:失配时的回退位置
# 【循环不变量】KMP 中 j 恒等于「模式串前 j 个字符与主串当前位置之前的后缀相等」
# 的长度;next 数组构造完成后所有前缀信息就绪
# 【递归终止】朴素:起点枚举完;KMP:主串扫描完或 j==m 匹配成功
# 【关键边界】空模式串两种写法都返回 0;构造 next 时失配回退 j = nxt[j-1](回退
# 到更短前缀);起点范围 range(n-m+1);匹配时主串不回溯
# 【复杂度】朴素 O(n·m);KMP O(n+m) 时间、O(m) 空间(next 数组)
# 28. 找出字符串中第一个匹配项的下标(朴素版):逐个起点尝试匹配,O(n*m)
def str_str_naive(haystack, needle):
if needle == '':
return 0 # 空模式串规定返回 0
n, m = len(haystack), len(needle) # 主串与模式串长度
for i in range(n - m + 1): # 枚举所有可能的起点
if haystack[i:i + m] == needle: # 切片比较是否匹配
return i # 返回第一个匹配起点
return -1 # 找不到返回 -1
# KMP 版:匹配失败时主串不回退,用 next 数组跳过已匹配的前缀,复杂度 O(n+m)
def str_str_kmp(haystack, needle):
if needle == '':
return 0 # 空模式串返回 0
# 计算 next 数组:next[i] = 前缀串最长相等前后缀长度
m = len(needle)
nxt = [0] * m # next[i] 表示模式串前 i+1 个字符的最长相等前后缀长度
j = 0 # 当前匹配到的前缀长度
for i in range(1, m): # 从第 2 个字符开始构造 next
while j > 0 and needle[i] != needle[j]: # 失配就回退到上一个前缀位置
j = nxt[j - 1] # 利用已算出的 next 回退
if needle[i] == needle[j]: # 匹配上则前缀长度加 1
j += 1
nxt[i] = j # 记录当前位置的最长相等前后缀
# 匹配主串
j = 0
for i in range(len(haystack)): # 主串只前进不回退
while j > 0 and haystack[i] != needle[j]: # 失配:模式串指针回退
j = nxt[j - 1] # 跳到已匹配前缀的末尾
if haystack[i] == needle[j]: # 当前字符匹配
j += 1 # 模式串前进
if j == m: # 模式串完全匹配
return i - m + 1 # 返回匹配起点
return -1 # 找不到返回 -1
print('朴素:', str_str_naive('sadbutsad', 'sad')) # 0
print('朴素:', str_str_naive('leetcode', 'leeto')) # -1
print('KMP:', str_str_kmp('hello', 'll')) # 2
print('KMP:', str_str_kmp('ababcababc', 'abc')) # 2
print('KMP 空模式:', str_str_kmp('a', '')) # 0
朴素: 0 朴素: -1 KMP: 2 KMP: 2 KMP 空模式: 0
§4 回文类:125 / 680¶
125 验证回文串¶
思路:双指针从两端向中间,跳过非字母数字、忽略大小写:
while l < r:
while l < r and not s[l].isalnum(): l += 1
while l < r and not s[r].isalnum(): r -= 1
if s[l].lower() != s[r].lower(): return False
l += 1; r -= 1
680 验证回文串 II(最多删一个字符)¶
思路:双指针遇到不等时,只尝试删左或删右(两种分支之一):
$$\text{可行} = \text{is\_pal}(l+1, r) \lor \text{is\_pal}(l, r-1)$$
复杂度:$O(n)$,$O(1)$ 空间(每个分支最多再扫一遍)。
# ============== 125 验证回文串 / 680 验证回文串 II ==============
# 【题目目标】① 125:忽略大小写与非字母数字字符后,判断字符串是否回文;
# ② 680:最多删除一个字符后,字符串能否成为回文
# 【算法思路】双指针:125 从两端向中间扫描,先跳过 isalnum() 为假的字符,再
# 用 lower() 忽略大小写比较;680 双指针遇到第一个不等的字符时,只尝试
# 「删左」或「删右」两个分支,用辅助函数 ok(l, r) 判断剩余子串是否回文
# 【变量含义】s:输入字符串;l/r:左右指针;ok(l, r):判断子串 s[l:r+1] 是否回文
# 【循环不变量】125:指针相遇前,l 左侧与 r 右侧的已比较字符全部相等(忽略
# 大小写/无效字符);680:未出现不等之前 l、r 处字符对称相等
# 【递归终止】125 的 while l < r 相遇即结束;680 遇到第一个不等时直接返回两个
# 分支的或(外层扫描结束)
# 【关键边界】125 的跳过循环内部也要带 l < r 条件(防止指针越界);isalnum 先
# 判再取字符比较;680 只能删一个字符,分支深度不超过一层
# 【复杂度】两题均为 O(n) 时间、O(1) 空间
# 125. 验证回文串:忽略大小写与非字母数字字符,判断是否回文
# 思路:双指针从两端向中间,跳过无效字符后比较,全部相等即回文
def is_palindrome(s):
l, r = 0, len(s) - 1 # 左右指针指向两端
while l < r: # 未相遇就继续
while l < r and not s[l].isalnum(): # 左指针跳过非字母数字
l += 1
while l < r and not s[r].isalnum(): # 右指针跳过非字母数字
r -= 1
if s[l].lower() != s[r].lower(): # 忽略大小写比较
return False # 不相等则不是回文
l += 1 # 左指针右移
r -= 1 # 右指针左移
return True # 全部相等 → 是回文
# 680. 验证回文串 II:最多删除一个字符后能否成为回文
# 思路:双指针遇到第一个不等时,只尝试删左或删右两种分支,任一分支是回文即可
def valid_palindrome_ii(s):
def ok(l, r): # 判断子串 s[l:r+1] 是否回文
while l < r:
if s[l] != s[r]: # 出现不等 → 不是回文
return False
l += 1
r -= 1
return True # 全部相等 → 是回文
l, r = 0, len(s) - 1 # 左右指针指向两端
while l < r: # 从两端向中间扫描
if s[l] != s[r]: # 第一次遇到不相等
# 删左 or 删右
return ok(l + 1, r) or ok(l, r - 1) # 删掉左字符或右字符,任一可行即成功
l += 1 # 相等则继续向中间靠拢
r -= 1
return True # 全程相等 → 已是回文
print('125:', is_palindrome('A man, a plan, a canal: Panama')) # True
print('125:', is_palindrome('race a car')) # False
print('125:', is_palindrome(' ')) # True
print('680:', valid_palindrome_ii('abca')) # True(删 c)
print('680:', valid_palindrome_ii('abc')) # False
print('680:', valid_palindrome_ii('ab')) # True
125: True 125: False 125: True 680: True 680: False 680: True
§5 计数/哈希类:242 / 49 / 387¶
242 有效的字母异位词¶
两种写法:
$$\text{Counter}(s) = \text{Counter}(t) \quad \text{或} \quad \text{sorted}(s) = \text{sorted}(t)$$
49 字母异位词分组¶
分组键:排序后的字符串(或字符计数元组):
$$\text{key} = \text{sorted}(\text{word}) \Rightarrow \text{同字母异序词共享 key}$$
复杂度:$O(n \cdot k \log k)$(k 为单词平均长度)。
387 字符串中的第一个唯一字符¶
思路:Counter 统计 → 再扫一遍找第一个频次为 1 的:$O(n)$ 时间,$O(1)$ 空间(字母表固定 26)。
# ============== 计数哈希三题:242 / 49 / 387 ==============
# 【题目目标】① 242:判断两个字符串是否为字母异位词;② 49:把互为字母异位词
# 的单词分到同一组;③ 387:找出第一个只出现一次的字符的下标
# 【算法思路】计数哈希三件套:242 直接比较两个 Counter 是否相等(字符种类与
# 个数完全相同);49 用「排序后的字符串」作为分组键——互为异位词的
# 单词排序后完全相同,放进同一个 defaultdict(list);387 先 Counter 统计
# 频次,再按原顺序扫描一遍,返回第一个频次为 1 的字符下标
# 【变量含义】s/t:两个字符串;strs:单词列表;d:排序键 → 单词列表的字典;
# w:当前单词;key:排序后的单词;cnt:频次表;ch/i:字符与其下标
# 【循环不变量】49 的 d 中,同一分组的单词排序后 key 完全相同;387 的 cnt 建成
# 后不再变化,第二轮扫描只读
# 【递归终止】无递归;遍历完成即结束
# 【关键边界】242 长度不同的串可直接提前返回 False;387 找不到频次为 1 的字符
# 返回 -1;49 空输入返回空列表;387 的 Counter 构造是 O(n)
# 【复杂度】242:O(n);49:O(ΣL·log L)(对每个单词排序);387:O(n);
# 空间均为 O(n)
# 计数哈希三题:242 异位词比计数相等;49 分组用排序串当 key;387 第一个唯一字符先计数再扫一遍
from collections import Counter, defaultdict
# 242. 有效的字母异位词:两个字符串的字符种类与个数完全相同
def is_anagram(s, t):
return Counter(s) == Counter(t) # 直接比较两串的字符计数是否相等
# 49. 字母异位词分组:把互为异位词的单词分到同一组
# 思路:排序后的字符串作为分组键,同字母异序词排序后完全相同
def group_anagrams(strs):
d = defaultdict(list) # 键 → 单词列表
for w in strs: # 遍历每个单词
key = ''.join(sorted(w)) # 排序作分组键
d[key].append(w) # 放入对应分组
return list(d.values()) # 返回所有分组
# 387. 字符串中的第一个唯一字符:找出第一个出现次数为 1 的字符下标
# 思路:先 Counter 统计频次,再扫一遍找第一个频次为 1 的字符
def first_uniq_char(s):
cnt = Counter(s) # 统计每个字符出现次数
for i, ch in enumerate(s): # 按原顺序扫描
if cnt[ch] == 1: # 出现次数为 1 → 唯一字符
return i # 返回其下标
return -1 # 没有唯一字符返回 -1
print('242:', is_anagram('anagram', 'nagaram')) # True
print('242:', is_anagram('rat', 'car')) # False
print('49:', group_anagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']))
print('387:', first_uniq_char('leetcode')) # 0
print('387:', first_uniq_char('loveleetcode')) # 2
print('387:', first_uniq_char('aabb')) # -1
242: True 242: False 49: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']] 387: 0 387: 2 387: -1
§6 字符串转换:8 字符串转换整数(atoi)¶
题目:实现 atoi:忽略前导空格 → 处理正负号 → 读数字 → 越界截断到 $[2^{31}, 2^{31}-1]$。
公式:
$$\text{num} = \text{num} \times 10 + (ch - '0')$$
$$\text{clamp: } \begin{cases} -2^{31} & \text{num} < -2^{31} \\ 2^{31} - 1 & \text{num} > 2^{31} - 1 \end{cases}$$
复杂度:$O(n)$。
⚠️ 边界:
+号允许一次;+-12非法返回 0;只有数字可读时部分读取。
# ============== 8 字符串转换整数 atoi(状态机 + 越界截断) ==============
# 【题目目标】实现字符串转 32 位有符号整数:跳过前导空格 → 读取可选正负号 →
# 读取连续数字 → 越界时截断到 [INT_MIN, INT_MAX];读到非数字即停止
# 【算法思路】状态机式顺序处理:① 跳过前导空格;② 读符号(最多出现一次);
# ③ 逐位读数字并累加 num = num*10 + digit,每步与边界比较,越界立即
# 返回 INT_MAX/INT_MIN 截断;④ 遇到非数字或串尾停止
# 【变量含义】s:输入字符串;i:扫描指针;n:串长;sign:符号(±1);num:累积
# 数值;INT_MAX/INT_MIN:32 位有符号整数边界
# 【循环不变量】num 恒等于已读取数字形成的十进制值(尚未乘 sign)
# 【递归终止】while 循环读到非数字字符或 i==n 停止
# 【关键边界】越界判断须在乘法前完成(num > (INT_MAX - digit)//10 时截断),避免
# 数值本身先溢出;只有符号没有数字(如 '+-12'、'-')应返回 0;正负号
# 后必须紧跟数字才有效
# 【复杂度】O(n) 时间、O(1) 空间
# 8. 字符串转换整数 atoi:按状态机依次处理空格、正负号、数字,越界截断到 32 位范围
# 边界:前导空格可忽略;正负号最多一次;读到非数字即停止;超出 [INT_MIN, INT_MAX] 时截断
def my_atoi(s):
i, n = 0, len(s) # 扫描指针与字符串长度
while i < n and s[i] == ' ': # 1. 跳过空格
i += 1 # 指针后移
sign = 1 # 符号位,默认正数
if i < n and (s[i] == '+' or s[i] == '-'): # 出现正负号
if s[i] == '-': # 是负号
sign = -1 # 标记为负数
i += 1 # 跳过符号位
num = 0 # 累积的数值
INT_MAX, INT_MIN = 2 ** 31 - 1, -2 ** 31 # 32 位有符号整数范围
while i < n and s[i].isdigit(): # 2. 读数字
num = num * 10 + (ord(s[i]) - ord('0')) # 逐位累加:num = num*10 + 当前位
if sign * num >= INT_MAX: # 3. 越界提前截断
return INT_MAX # 超上限截断为 INT_MAX
if sign * num <= INT_MIN: # 低于下限
return INT_MIN # 截断为 INT_MIN
i += 1 # 继续读下一位
return sign * num # 带上符号返回结果
print('42:', my_atoi('42')) # 42
print('-42:', my_atoi(' -42')) # -42
print('4193:', my_atoi('4193 with words')) # 4193
print('0:', my_atoi('words and 987')) # 0
print('max:', my_atoi('-91283472332')) # -2147483648
print('0:', my_atoi('+-12')) # 0
42: 42 -42: -42 4193: 4193 0: 0 max: -2147483648 0: 0
§7 常见 bug 与边界(面试踩坑区)¶
- Python 字符串不可变:原地修改必须转 list,改完 join 回来
- 循环拼接 O(n²):
s += ch在循环里每次都新建对象——用parts.append(ch)+''.join(parts) - split 默认行为:
' a b '.split()→['a','b'](自动去空白去空串);split(' ')则保留空串——151 用前者 - 大小写:125 用
.lower();字母数字判断用.isalnum()(含数字) - KMP next 数组下标:
j = nxt[j - 1]循环必须写(否则死循环) - atoi 的越界判断时机:先乘 10 再加就溢出,要在每次累加后立即判
- 空串/单字符:
''模式返回 0;'a'是回文、'ab'删一个也是
§9 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 题)¶
- 1. 反转字符串(LeetCode 344)
- 2. 反转字符串中的单词(151)
- 3. 验证回文串(125)
- 4. 有效的字母异位词(242)
- 5. 字符串中的第一个唯一字符(387)
- 6. 找出字符串中第一个匹配项的下标(28)
- 7. 最长公共前缀(14)
- 8. 字符串转换整数 atoi(8)
- 9. 重复的子字符串(459)
- 10. 整数反转(7)
L2 进阶(10 题)¶
- 11. 字母异位词分组(49)
- 12. 验证回文串 II(680)
- 13. 找到字符串中所有字母异位词(438)
- 14. 字符串压缩(443)
- 15. Z 字形变换(6)
- 16. 简化路径(71,栈)
- 17. 单词规律(290,双向映射)
- 18. 字符串相乘(43,大数模拟)
- 19. 反转字符串中的单词 III(557)
- 20. 罗马数字转整数(13)
L3 挑战(5 题)¶
- 21. 最短回文串(214,KMP 应用)
- 22. 编辑距离(72,见主题 8)
- 23. 通配符匹配(44,DP)
- 24. 最小覆盖子串(76,滑动窗口,见主题 2)
- 25. 解码方法(91,DP)
自测要点¶
- 5 分钟内盲写:344 + 125 + 242 + 28(朴素版)
- 能讲 KMP 的 next 数组含义与主串不回退原理
- 会写 atoi 的完整状态机(空格/符号/数字/越界)
附录:参考与结课寄语¶
- 《算法导论》第 32 章:字符串匹配(KMP/RK)
- LeetCode 分类题单:字符串
🎉 本系列完成:01-数据结构与算法 13 个主题全部收尾¶
回看路线:数组哈希 → 双指针滑动窗口 → 链表 → 栈队列 → 二分 → 二叉树 → 回溯 → 动态规划 → 贪心 → 图 → 堆 → 位运算 → 字符串。
下一步:02-机器学习/(线性回归/逻辑回归/SVM/树模型……)与 03-深度学习/(CNN/RNN/Transformer……)教学系列同样按此深度推进。
💡 本主题验收:
高频题单.md「字符串」一节全部打勾;届时 01 系列 13 份 notebook + 题单即构成秋招算法完整兵器库。
✍️ §10.1 手算 Rabin-Karp 滚动哈希:hash("bcd") 从 "abc" 滚出来¶
滚动哈希 $H_{t+1}=\big((H_t-w_0\cdot b^{L-1})\cdot b+w_{L}\big)\bmod M$——"abc"→"bcd" 手算,验证窗口滑动一步的哈希更新。
设定:基数 $b=10$,模 $M=1000$,窗口长 3。
第 1 步:$H(abc)=(97\times10^2+98\times10+99)\bmod1000=779$
第 2 步:滚动一步(去掉头部 a=97,加入尾部 d=100)
$$H(bcd)=\big((779-97\times10^2)\times10+100\big)\bmod1000=890$$
第 3 步:直接验证 $H(bcd)=(98\times10^2+99\times10+100)\bmod1000=890$ ✓
手算收获:
- 滚动哈希把"每次重算子串"从 $O(L)$ 降到 $O(1)$——整个 Rabin-Karp 匹配 $O(n)$(§10 Rabin-Karp 代码)
- 模 $M$ 引入哈希碰撞:$H$ 相等还要逐字符确认(面试必提);大 $b$(如 131)+ 大质数模降低碰撞率
- 模运算下减法要加 $M$ 再取模防负数(Python
%恒正,C++ 需注意) - 变体:最长重复子串、字符串比较加速都用它——"窗口内多哈希比较"的通用技巧
下面 numpy 复算。
# ---- §10.1 验证:numpy 复算滚动哈希 ----
base, mod = 10, 1000
def rh(s):
h = 0
for ch in s:
h = (h * base + ord(ch)) % mod
return h
h_abc = rh('abc')
h_bcd = rh('bcd')
h_roll = ((h_abc - ord('a') * base ** 2) * base + ord('d')) % mod
print(f'hash(abc) = {h_abc}, hash(bcd) = {h_bcd}, 滚动得到 = {h_roll}')
assert h_abc == 779 and h_bcd == 890 and h_roll == h_bcd
print('\n✓ 与手算一致')
# ============== Rabin-Karp 滚动哈希匹配 ==============
# 【题目目标】用滚动哈希在主串 haystack 中找模式串 needle 首次出现的下标,
# 找不到返回 -1(KMP 之外的另一种匹配思路)
# 【算法思路】把子串比较变成哈希比较:先计算模式串的哈希 target 与主串第一个
# 窗口的哈希;窗口每次右移一位时 O(1) 更新哈希(减去最左字符的贡献 +
# 加入新字符);哈希相等只是候选,命中后仍需逐字符确认,防止哈希碰撞
# 【变量含义】haystack/needle:主串与模式串;n/m:长度;BASE/MOD:进制基数与
# 大质数模数(减少碰撞);target:模式串哈希;power:BASE^(m-1)(最左
# 字符的权重,窗口滑动时减去);h:当前窗口哈希;l/r:窗口左右边界
# 【循环不变量】h 恒等于窗口 [l, l+m) 子串的哈希值,随窗口滑动同步更新
# 【递归终止】无递归;窗口从 0 滑动到 n-m 结束
# 【关键边界】空模式串返回 0;m > n 直接返回 -1;每步取模防溢出;哈希相等时
# 必须逐字符复核(碰撞只会导致最坏退化 O(n·m),期望 O(n+m))
# 【复杂度】期望 O(n+m) 时间、O(1) 额外空间
# Rabin-Karp 字符串匹配:把子串比较变成哈希比较,窗口滑动时 O(1) 更新哈希
# 哈希相等只是候选,命中后仍需逐字符确认,防止哈希碰撞
def rabin_karp(haystack, needle):
# Rabin-Karp:滚动哈希在 haystack 中找 needle 首次出现下标,找不到返回 -1
n, m = len(haystack), len(needle) # 主串与模式串长度
if m == 0:
return 0 # 空模式串返回 0
if m > n:
return -1 # 模式串比主串长,不可能匹配
BASE, MOD = 131, 10 ** 9 + 7 # 进制基数与模数(取大质数减少碰撞)
# 目标哈希 + 最高位权重 base^(m-1)
target = 0
for ch in needle:
target = (target * BASE + ord(ch)) % MOD # 计算模式串的哈希
power = pow(BASE, m - 1, MOD) # 最高位权重,供滑动窗口减去最左字符用
# 第一个窗口
h = 0
for ch in haystack[:m]:
h = (h * BASE + ord(ch)) % MOD # 计算主串第一个窗口的哈希
if h == target and haystack[:m] == needle:
return 0 # 首个窗口就命中(并逐字符确认)
for l in range(n - m): # 窗口向右滑动 n-m 次
r = l + m # 窗口右边界
# 窗口右滑:去掉最左字符(权重 power),加入最右字符
h = ((h - ord(haystack[l]) * power) * BASE + ord(haystack[r])) % MOD # O(1) 更新滚动哈希
if h == target and haystack[l + 1:r + 1] == needle: # 命中后逐字符确认
return l + 1 # 返回匹配起点
return -1 # 全部窗口都没命中返回 -1
print('RK:', rabin_karp('hello', 'll'), '| 内置 find:', 'hello'.find('ll')) # 期望 2 / 2
print('RK:', rabin_karp('aaaaa', 'bba'), '| 内置 find:', 'aaaaa'.find('bba')) # 期望 -1 / -1
print('RK 空模式:', rabin_karp('abc', '')) # 期望 0
hay = 'a' * 10000 + 'b'
nd = 'a' * 5000 + 'b'
print('RK 长串:', rabin_karp(hay, nd), '| 内置 find:', hay.find(nd)) # 期望 5000 / 5000
RK: 2 | 内置 find: 2 RK: -1 | 内置 find: -1 RK 空模式: 0 RK 长串: 5000 | 内置 find: 5000
# ============== 14 最长公共前缀(垂直扫描) ==============
# 【题目目标】找字符串数组中所有字符串共同的最长前缀(没有则返回空串)
# 【算法思路】垂直扫描:以第一个字符串为基准,逐列(同一位置)比较所有字符串
# 的字符——遇到某串到头或字符不一致,立即返回已积累的前缀;每列全部
# 一致则把该字符追加到答案
# 【变量含义】strs:字符串数组;first:基准串;i:列号(第 i 个字符位置);
# s:数组中的字符串;prefix:已积累的公共前缀
# 【循环不变量】已积累的 prefix 是所有字符串的公共前缀(前 i 列全部一致)
# 【递归终止】i 到达基准串长度(最短串之一)、或某一串长度不足、或字符不一致
# 时终止
# 【关键边界】空列表返回空串;比较循环的下界取基准串长度,访问 strs[j][i] 前
# 先判 i < len(s) 防越界;也可以用 all(s.startswith(prefix)) 风格简化
# 【复杂度】O(S·L)(S 为串数、L 为最短串长)、O(1) 额外空间
# 14. 最长公共前缀:所有字符串共同的前缀
# 思路:垂直扫描——以第一个字符串为基准,逐列比较所有字符串同一位置的字符
def longest_common_prefix(strs):
# 垂直扫描:逐列比较所有字符串同一下标的字符,遇到不同或越界即返回
if not strs:
return '' # 空输入直接返回空串
for i in range(len(strs[0])): # 按第一个字符串逐列扫描
ch = strs[0][i] # 基准字符
for s in strs[1:]: # 与其他所有字符串比较
if i >= len(s) or s[i] != ch: # 某个串更短或字符不同 → 前缀到此为止
return strs[0][:i] # 返回前 i 个字符作为公共前缀
return strs[0] # 全部列都相同 → 第一个字符串即公共前缀
print('14:', longest_common_prefix(['flower', 'flow', 'flight'])) # 期望 fl
print('14:', repr(longest_common_prefix([]))) # 期望 ''(空列表)
print('14:', longest_common_prefix(['a'])) # 期望 a
print('14:', repr(longest_common_prefix(['dog', 'racecar', 'car']))) # 期望 ''
14: fl 14: '' 14: a 14: ''
# ============== 151 反转单词(原地双反转版 + split 对照) ==============
# 【题目目标】151 的省空间实现:反转字符串中单词的顺序,同时去掉首尾与中间的
# 多余空格;并附 split 对照版用于交叉验证
# 【算法思路】三步原地法:① strip 去首尾空格后整体反转(单词顺序颠倒、拼写也
# 颠倒);② 逐词反转恢复拼写(此时单词顺序已正确);③ write 指针从
# 左到右搬运字符、单词之间只保留一个空格(原地压缩多余空格);对照版
# 直接用 split + [::-1] + join
# 【变量含义】s:输入字符串;chars:字符列表(字符串不可变需转 list);n:长度;
# reverse_range(i,j):反转 chars[i:j](含 i 不含 j);i/j:扫描指针;
# write:写指针(压缩空格后);reverse_words_split:对照版函数
# 【循环不变量】三步各自完成后状态确定:整体反转 → 单词拼写恢复 → 空格压缩完
# 成后,chars[:write] 即为最终答案
# 【递归终止】无递归;while 扫描到数组末尾结束
# 【关键边界】必须先把字符串转成 list(不可变);首尾空格靠 strip 处理;单词间
# 多个连续空格由 write 指针压缩成一个;空串或全空格输入返回空串
# 【复杂度】原地版 O(n) 时间、O(1) 额外空间;对照版 O(n) 时间、O(n) 空间
# 151. 反转字符串中的单词(原地双反转版):不用 split,省空间
# 三步:整体反转(单词顺序颠倒)→ 逐词反转(拼写恢复)→ write 指针压缩多余空格
def reverse_words(s):
# 省空间双反转版:整体反转 → 逐词反转 → write 指针原地压缩空格
# 1) strip 去首尾空格,整体反转(单词顺序颠倒)
# 2) 逐词 swap 反转(单词拼写恢复原序,此时顺序已正确)
# 3) write 指针从左到右搬运,单词间只保留一个空格
chars = list(s.strip()) # 去掉首尾空格后转成字符列表(字符串不可变,需转 list)
n = len(chars) # 字符个数
def reverse_range(i, j): # 反转 chars[i:j](含 i,不含 j)
while i < j - 1: # 双指针从两端向中间交换
chars[i], chars[j - 1] = chars[j - 1], chars[i] # 交换两端字符
i += 1 # 左指针右移
j -= 1 # 右指针左移
reverse_range(0, n) # 1) 整体反转
i = 0 # 扫描指针
while i < n: # 2) 逐词反转
while i < n and chars[i] == ' ': # 跳过单词间的空格
i += 1
j = i # 单词起点
while j < n and chars[j] != ' ': # 找到单词结尾
j += 1
reverse_range(i, j) # 反转这个单词,恢复拼写
i = j # 从单词末尾继续
write = 0 # 3) 压缩空格:单词间只留一个空格
i = 0 # 读指针
while i < n: # 扫描整个字符列表
if chars[i] != ' ': # 遇到单词字符
if write > 0: # 不是第一个单词:前面补一个空格
chars[write] = ' '
write += 1
while i < n and chars[i] != ' ': # 复制整个单词
chars[write] = chars[i] # 搬到 write 位置
write += 1
i += 1
else:
i += 1 # 多余空格直接跳过
return ''.join(chars[:write]) # 只取 write 之前的有效部分
# 对照版:用 split 直观实现,用于验证双反转版的结果
def reverse_words_split(s):
# 直观版:手动 split + join(与双反转结果对照)
return ' '.join(reversed(s.split())) # split 拆词、reversed 反转、空格拼接
s1 = 'the sky is blue'
print('151:', repr(reverse_words(s1)), '| 对照:', repr(reverse_words_split(s1))) # 期望 blue is sky the
s2 = ' hello world '
print('151:', repr(reverse_words(s2)), '| 对照:', repr(reverse_words_split(s2))) # 期望 world hello
print('151:', repr(reverse_words('a good example'))) # 期望 example good a
print('151 全空格:', repr(reverse_words(' '))) # 期望 ''
151: 'blue is sky the' | 对照: 'blue is sky the' 151: 'world hello' | 对照: 'world hello' 151: 'example good a' 151 全空格: ''