🏠 总目录📚 本教程 08 · 字符串与输入:脏输入也要有边界 ← →
📑 本页目录(点开跳转)

08 · 字符串与输入:脏输入也要有边界

⏱ 10 分钟 | atoi、最长无重复子串、字符流

🎯 一句话

字符串题的本质常常是一个小状态机:当前读到哪里、已经确认了什么、下一类字符还允不允许出现。

屏幕上看着一样,程序数的是什么?

复制两个看起来相同的 é,程序却可能把它们判断为不同。上一章先约定整数的位宽,这里先约定字符串的计数单位。

同一个可见字形的两种写法,UTF-8 字节用十六进制表示
写法Unicode 码点UTF-8 字节
预组成的 éU+00E9,1 个C3 A9,2 个
e 加组合重音U+0065 U+0301,2 个65 CC 81,3 个

本章的示例使用 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 会把十进制数的各位左移一格,再加当前数字就填上新的个位。

用 " -306g7" 跟踪解析过程,下标从 0 开始
读到状态变化
下标 0、1 的空格跳过,下一处是 2。
下标 2 的 -记下负号,下一处是 3。
3、0、60 × 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 记住每个码点最近出现的位置。新码点若和窗内旧码点冲突,就从旧位置后面继续。

读一遍 xyyx,每步先判断旧位置,再改记录
右端读到左端怎么走剩余窗口
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,把双方归一化后再查,匹配会成功,返回的是归一化后的下标。


⚡ 走神救援

下一步: 回到 00 · 怎么刷代码题,挑一题遮住代码重写。

继续: 附录A · 速查

打卡记录保存在你的浏览器里,首页能看到总进度