📑 本页目录(点开跳转)
08 · 字符串与输入:脏输入也要有边界
⏱ 10 分钟 | atoi、最长无重复子串、字符流
🎯 一句话
字符串题的本质常常是一个小状态机:当前读到哪里、已经确认了什么、下一类字符还允不允许出现。
屏幕上看着一样,程序数的是什么?
复制两个看起来相同的 é,程序却可能把它们判断为不同。上一章先约定整数的位宽,这里先约定字符串的计数单位。
| 写法 | Unicode 码点 | UTF-8 字节 |
|---|---|---|
| 预组成的 é | U+00E9,1 个 | C3 A9,2 个 |
| e 加组合重音 | U+0065 U+0301,2 个 | 65 CC 81,3 个 |
- 码点(code point)是 Unicode 编号,
U+后写十六进制数字。Python 的str按码点索引,所以两种写法的len()分别是 1 和 2。 - 编码(encoding)规定怎样把文本变成字节序列。UTF-8 中,这两个例子的字节长度分别为 2 和 3;用
len(text.encode("utf-8"))才能得到这个长度。 - 字素簇(grapheme cluster)是一种切分用户感知字符的单位。这两种写法各是一个字素簇;按码点截取组合写法的第一项,只会留下
e。Unicode 文本分段规范
本章的示例使用 str,按原有码点比较,不自动做 Unicode 归一化。若业务规定两种 é 必须相等,可以先对双方做 NFC 归一化,例如让 e 与组合重音合成同一个码点。归一化可能改变长度或下标,返回原串坐标时需要另外保留位置关系。字素簇切分仍是单独的一步。Unicode 归一化规范
来自文件或网络的 bytes 先按约定编码解码。举例说,b"\xc3" 缺了后续字节,按 UTF-8 严格解码会抛出 UnicodeDecodeError。这是解码失败,应和解码成功但字段不符合解析规则区分开。Python Unicode 指南
🧩 题 1:把字符串转换成整数(atoi)
先约定本题输入规则:前导空白只接受 ASCII 空格,数字只接受 0–9,结果限制为 32 位有符号整数。isdigit() 还接受 ² 等 Unicode 字符,但 int("²") 会报错;若题目另有 Unicode 约定,应单独实现并验证。
顺序固定:跳空格 → 读正负号 → 连续读数字 → 处理溢出。任何一步不符合规则就停止,而不是“尽量猜”。
逐位读数,读到第一个不合规字符就停
收到文本 " -306g7" 时,程序得先分清哪些位置属于整数。这里允许跳过开头的 ASCII 空格(U+0020),接着读至多一个 ASCII + 或 -,随后必须是连续的 ASCII 十进制数字。ASCII 是一套字符编码标准,本例只选它的空格、符号和十个数字作为合法输入。开头的制表符、全角数字和 Unicode 负号都不纳入这个规则。
代码里的 index 是下一处待读下标,sign 记录符号,value 是当前绝对值。已有值乘 10 会把十进制数的各位左移一格,再加当前数字就填上新的个位。
| 读到 | 状态变化 |
|---|---|
| 下标 0、1 的空格 | 跳过,下一处是 2。 |
| 下标 2 的 - | 记下负号,下一处是 3。 |
| 3、0、6 | 0 × 10 + 3 = 3;3 × 10 + 0 = 30;30 × 10 + 6 = 306。 |
| 下标 6 的 g | 停止,后面的 7 不参与。加回符号得 −306。 |
结果要夹在 −2³¹(−2147483648)与 2³¹−1(2147483647)之间。代码最后用 min 压住上界,再用 max 抬到下界。比如 "-2147483649" 的前缀解析值比下界小 1,返回 −2147483648。
def my_atoi(text):
index, sign, value = 0, 1, 0
while index < len(text) and text[index] == ' ':
index += 1
if index < len(text) and text[index] in '+-':
sign = -1 if text[index] == '-' else 1
index += 1
while index < len(text) and '0' <= text[index] <= '9':
value = value * 10 + int(text[index])
index += 1
value *= sign
return max(-(2**31), min(2**31 - 1, value))
assert my_atoi(' -42x') == -42
assert my_atoi('words and 9') == 0
assert my_atoi('91283472332') == 2**31 - 1
返回值的边界。开头没有合法数字时返回 0,比如空串、只剩符号或遇到连续符号。"0" 也返回 0。夹紧后的最大值同样无法区分原数是否越界。若业务需要校验整个字段或区分这些状态,须另外定义校验和错误返回规则。
扫描次数和算术成本。输入有 n 个码点,扫描位置最多前进 n 次。原示例先累加完整的 Python 整数再夹紧。若数字前缀有 d 位,最坏要保存 O(d) 位量级的大整数;逐位乘 10 和加一位数字随当前整数宽度增长,最坏累计 O(d²) 位工作量。扫描线性只说明每个位置读几次,实际耗时还要计入这部分运算。
🧩 题 2:最长不含重复字符的子字符串
窗口的左边界只向右走。新字符上一次出现的位置仍在窗口内时,就把左边界跳到那个位置的后一格。
找到重复项后,先问旧位置还在窗口里吗?
试着从 xyyx 挑出一段连续且无重复的码点。对子串逐段重查会多次看同一个位置。滑动窗口(sliding window)用 left、right 标出当前连续片段的两端,并用 last_seen 记住每个码点最近出现的位置。新码点若和窗内旧码点冲突,就从旧位置后面继续。
| 右端读到 | 左端怎么走 | 剩余窗口 |
|---|---|---|
| 0,x | 首次出现,左端为 0。 | x,长度 1 |
| 1,y | 首次出现,左端仍为 0。 | xy,长度 2 |
| 2,y | 旧 y 在 1,左端跳到 2。 | y,长度 1 |
| 3,x | 旧 x 在 0,已经出窗,左端保持 2。 | yx,长度 2 |
端点都算进长度,所以最后一步是 3 − 2 + 1 = 2。这一步若直接改成 left = 0 + 1,两个 y 会重新一起进入窗口。代码的 >= left 检查就是为了避免这个错误。
函数返回长度;空字符串返回 0。按哈希查询和写入平均常数时间计,扫描 n 个码点花 O(n) 时间,字典为 u 个不同码点各存一个位置,额外空间 O(u)。例如 "甲e\u0301甲" 的最长无重复窗口有 3 个码点。若题目改成按字素簇计数,输入会先切成「甲、e 加重音、甲」三项,这个例子的最长窗口只有 2 项。
def longest_unique(text):
last_seen, left, best = {}, 0, 0
for right, char in enumerate(text):
if char in last_seen and last_seen[char] >= left:
left = last_seen[char] + 1
last_seen[char] = right
best = max(best, right - left + 1)
return best
assert longest_unique('abcabcbb') == 3
assert longest_unique('bbbbb') == 1
可选深入:匹配指定模式时,失配了为什么不用从头比?
前缀表复用已经匹配的后缀
上一题找“无重复窗口”,这里换成查找固定模式第一次出现。对 pattern=ababaca,pi[i] 记录 pattern[:i+1] 的最长相等真前缀/后缀长度,得到 [0,0,1,2,3,0,1]。已匹配 ababa(q=5)后拿新字符 b 去比 c 失配,已知后缀 aba 也是前缀,于是 q 回退到 pi[4]=3,用同一个 b 比 pattern[3];文本位置不后退。若还失配,继续沿前缀表回退。
def prefix_table(pattern):
pi = [0] * len(pattern)
q = 0
for i in range(1, len(pattern)):
while q and pattern[i] != pattern[q]:
q = pi[q - 1]
if pattern[i] == pattern[q]:
q += 1
pi[i] = q
return pi
def kmp_find(text, pattern):
if not pattern:
return 0 # explicit API convention, same as str.find
pi, q = prefix_table(pattern), 0
for i, char in enumerate(text):
while q and char != pattern[q]:
q = pi[q - 1]
if char == pattern[q]:
q += 1
if q == len(pattern):
return i - q + 1
return -1
assert prefix_table("ababaca") == [0, 0, 1, 2, 3, 0, 1]
assert kmp_find("abababaca", "ababaca") == 2
from itertools import product
texts = ["".join(v) for n in range(7) for v in product("ab", repeat=n)]
patterns = ["".join(v) for n in range(4) for v in product("ab", repeat=n)]
for text in texts:
for pattern in patterns:
assert kmp_find(text, pattern) == text.find(pattern)
assert kmp_find("甲乙甲丙", "甲丙") == 2
print("前缀表/失配回退/空模式/无匹配/重叠前缀核验通过")
这里的匹配是原码点序列完全相同。代码用 q 表示已匹配的前缀长度,遇到失配时从 pi[q−1] 读出仍可复用的较短长度。设模式长 m、文本长 n,单位都为码点。空模式返回 0,非空模式找不到返回 −1,找到返回第一次出现的码点下标。比如在 "甲é乙" 中找 "乙" 返回 2;用 UTF-8 字节偏移表示则是 5,因为前面是 3 + 2 个字节。
q 每次匹配最多加一,回退只会减少 q;把加减次数一起摊算,建表 O(m)、扫描 O(n),额外表空间 O(m),不是看到 while 就乘成 O(nm)。示例按 Python 字符比较与索引,Unicode 归一化、字节偏移、多模式搜索都需另立约定。本节只解释这一个失配复用机制。原始依据:Knuth / Morris / Pratt,Fast Pattern Matching in Strings(1977)。
🧩 题 3:字符流中第一个不重复的字符
一边读一边维护两个事实:每个字符出现次数,以及第一次出现的顺序。队首若已经重复就淘汰。
队首不合格时,再看它后面的人
字符一个接一个到达,每次都重新数一遍会反复扫历史。这里让 Counter 记累计次数,让 deque 按到达顺序保存尚未弹出的记录。队列可以从末尾加人,也可以从头移人。某个码点已经出现两次,以后次数只会增加,所以队首一旦重复就能永久弹出。
| 新来的码点 | 清理后的队列 | 当前答案 |
|---|---|---|
| 甲 | 甲 | 甲 |
| 乙 | 甲、乙 | 甲 |
| 乙 | 甲、乙、乙 | 甲 |
| 甲 | 空。四个记录的码点都已重复。 | # |
| 丙 | 丙 | 丙 |
每次只插入一个 Unicode 码点,约定 # 为「目前没有答案」的保留标记。代码不验证参数;如果允许把 # 当普通输入,返回它就无法区分真实字符和空结果。
from collections import Counter, deque
class FirstUniqueStream:
def __init__(self):
self.counts, self.queue = Counter(), deque()
def insert(self, char):
self.counts[char] += 1
self.queue.append(char)
while self.queue and self.counts[self.queue[0]] > 1:
self.queue.popleft()
def first_unique(self):
return self.queue[0] if self.queue else '#'
stream = FirstUniqueStream()
for char in 'google':
stream.insert(char)
assert stream.first_unique() == 'l'
单次和总成本。一次插入可能弹出很多条。每条记录却只入队一次、最多出队一次,所以在哈希操作平均常数时间的前提下,n 次插入总共 O(n),平均到每次为 O(1),查询队首是 O(1)。原代码会把每次到达都入队。如果先来一个始终只出现一次的甲,之后一直来乙,甲会挡在队首,重复的乙仍然堆在后面。即使只有两种码点,队列最坏仍用 O(n) 空间。
复现输入边界检查
把本页四段示例代码按顺序放入同一个 Python 文件,再把下面的断言接到末尾。运行后若断言全部成立,最后会打印通过信息。
from unicodedata import normalize
cases = [
(" -306g7", -306), ("\t12", 0), ("12", 0), ("²", 0),
("-2147483648", -2147483648), ("-2147483649", -2147483648),
("2147483647", 2147483647), ("2147483648", 2147483647),
("", 0), ("+", 0), ("-+3", 0), ("23²8", 23), ("0", 0),
]
for text, expected in cases:
assert my_atoi(text) == expected, (text, expected)
composed, combined = "é", "e\u0301"
assert composed != combined and normalize("NFC", combined) == composed
assert (len(composed), len(combined)) == (1, 2)
assert (len(composed.encode("utf-8")), len(combined.encode("utf-8"))) == (2, 3)
try:
b"\xc3".decode("utf-8", errors="strict")
except UnicodeDecodeError:
pass
else:
raise AssertionError("incomplete UTF-8 was accepted")
assert longest_unique("xyyx") == 2
assert longest_unique("甲e\u0301甲") == 3
assert kmp_find(combined, composed) == -1
assert kmp_find("甲é乙", "乙") == 2
example_stream = FirstUniqueStream()
seen = []
for char in "甲乙乙甲丙":
example_stream.insert(char)
seen.append(example_stream.first_unique())
assert seen == ["甲", "甲", "甲", "#", "丙"]
print("输入边界与文本单位核验通过")
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| Python 会咬你的地方 09 · 容器、哈希与顺序 | ⭐ 题 3 靠的是 Counter + deque 和「第一次出现的顺序」。那一章讲这批容器各自保不保序:dict 从 3.7 起保证插入序,set 从来不保证,字符串集合的实际遍历顺序可能随哈希种子而变 |
附录速查把这些问题归到不同的不变量。做题前先写清输入的读取单位,再写清输出的含义,比如值、长度、位置或「暂无结果」。模型分词又定义了自己的单位 token。即使一个汉字占 3 个 UTF-8 字节,也不能据此确定 token 数,要用目标分词器和词表检查。
本节回顾
看到字符串解析题,先列出合法阶段,而不是先写一堆 if。阶段明确,边界自然会出现。
✅ 检查点
最长无重复子串为什么左边界从不回退?
👀 看答案
右边界已经向右扩展;回退左边界只会把已知会冲突的字符重新放回窗口,既无帮助又会重复计算。
预测 my_atoi(" +1234") 的返回值。全角 3 和最后的 4 会被读取为数字吗?
👀 看答案
返回 12。全角 3 不在 ASCII 0–9 内,扫描在这里停止,后面的 4 不会进入解析。
把组合写法的 e 加重音放进文本,再用预组成的 é 查找。它们看起来相同,原 KMP 能找到吗?
👀 看答案
找不到。原 KMP 比较的是码点,U+0065 U+0301 里没有 U+00E9。若输入规则允许 NFC,把双方归一化后再查,匹配会成功,返回的是归一化后的下标。
⚡ 走神救援
- atoi:空格、符号、数字、溢出四个阶段。
- 滑动窗口:左右边界都只向右,不回头。
- 字符流:次数负责判断重复,队列负责保留先后。
下一步: 回到 00 · 怎么刷代码题,挑一题遮住代码重写。
继续: 附录A · 速查