从算法到人工智能 · 第 7 课：字符串——被忽视的基本功
上一课我们用哈希表秒杀了"两数之和"，享受了一把"查找 O(1)"的快感。但你可能没意识到：你写代码、读文件、处理用户输入、爬网页、调 API 时，碰到最多的数据类型，其实是字符串。
字符串很"狡猾"：它看起来最简单——不就是一串字符吗？但里面藏着的坑和门道一点不比哈希表少。面试里那些"最长回文子串""无重复字符的最长子串""字符串匹配"，全是围绕它转的。
这一课，我们把字符串这层窗户纸捅破：它到底是怎么存的、为什么"改不了"、怎么切片、怎么匹配，再学两个面试高频套路——KMP 的直觉和滑动窗口。
一、字符串到底是什么：一串"改不了"的字符
在 Python 里，字符串就是一串字符，写法随便你挑：
s1 = 'hello'
s2 = "hello"
s3 = """hello"""
print(s1 == s2 == s3) # True，三种写法一个东西但字符串有个特别关键的性质，很多人栽在这上面：
字符串是不可变的（immutable）。一旦创建，就不能修改里面的任何一个字符。
什么意思？看这段代码：
s = "hello"
s[0] = "H" # 报错！TypeError: 'str' object does not support item assignment你想把开头的 h 改成大写 H，Python 直接拒绝。那问题来了——你平时明明写过这样的代码，它怎么就"改"了？
s = "hello"
s = "Hello" # 这行没报错呀？注意，这不是修改，是重新赋值：你没有动原来的 "hello" 那一串字符，而是新造了一个字符串 "Hello"，让变量名 s 指向它。原来那个 "hello" 还躺在内存里（没人引用了，等垃圾回收）。
为什么非要"不可变"？
因为字符串要当字典的键、要被缓存、要被到处引用。如果谁都能随手改它，哈希值就乱了，字典直接崩。不可变，换来的是安全和可预测。 还记得上一课说的吗——列表不能当字典键，元组能，就是因为元组不可变。字符串跟元组是一伙的。
代价：如果你想"原地修改"一个长字符串，反复 s = s + "x"，每次都新造一个字符串，代价是 O(n)。所以：
# 慢：每次 + 都新造一个字符串，O(n²)
s = ""
for i in range(10000):
s += str(i)
# 快：把碎片放进列表，最后一次性 join，O(n)
parts = []
for i in range(10000):
parts.append(str(i))
s = "".join(parts)这是字符串的第一课心法：拼接别用 +=，用 join。
二、切片：字符串最常用的"手术刀"
Python 字符串最爽的地方，就是切片（slice）——用下标抓出任意一段。
s = "abcdef"
s[0] # 'a' 取一个字符
s[0:3] # 'abc' 从 0 到 3（不含 3）
s[:3] # 'abc' 从头到 3
s[3:] # 'def' 从 3 到尾
s[-1] # 'f' 倒数第一个
s[-3:] # 'def' 倒数三个
s[::2] # 'ace' 从头到尾，隔一个取一个
s[::-1] # 'fedcba' 反转！这是最帅的用法切片的完整格式是 s[start:stop:step]，记住三条规则：
- 顾头不顾尾：
s[0:3]取下标 0、1、2，不含 3。 - 下标能是负数：
-1是最后一个，-2是倒数第二个。 - step 能是负数：
s[::-1]一步一退，就是反转。
切片和"不可变"是绝配——切片永远是"复制"出一段新字符串，绝不动原字符串。所以你随便切，原串永远安全。
三、常用方法：字符串的"十八般兵器"
Python 给字符串配了一整套方法，常用的记住这些就够用：
s = " Hello, World "
s.strip() # 'Hello, World' 去首尾空白
s.lower() # ' hello, world ' 全转小写
s.upper() # ' HELLO, WORLD ' 全转大写
s.replace("World", "Python") # ' Hello, Python ' 替换
s.split(",") # [' Hello', ' World '] 按逗号切分
"|".join(["a", "b"]) # 'a|b' 用竖线拼接
s.find("World") # 8 找子串位置，找不到返回 -1
"World" in s # True 判断子串在不在（O(n) 但很快）
s.count("o") # 2 统计出现次数
s.startswith(" He") # True 判断开头
s.endswith("d ") # True 判断结尾
s.isdigit() # False 是不是纯数字
"abc".isalpha() # True 是不是纯字母两个高频坑，记牢：
# 坑 1：这些方法都是"返回新串"，原串不变
s = "hello"
s.upper() # 这行啥也没改
print(s) # 还是 'hello'，因为你没接住返回值
s = s.upper() # 要这样才生效
# 坑 2：split 后是列表，遍历要用下标或 in
words = "a b c".split()
print(words) # ['a', 'b', 'c']
print("b" in words) # True，别拿 in 去查子串，那是查元素记住：字符串方法几乎都是"返回新串"，想要结果，记得接住返回值。
四、字符串匹配：从暴力到 KMP 的直觉
这是字符串里最核心的算法问题——在一个长字符串里，找某个短字符串（模式）第一次出现的位置。
text = "ababcabcab"
pattern = "abcab"
# 问：pattern 在 text 里第几个位置出现？笨办法：暴力匹配 O(n×m)
从头到尾，每个位置都试着"对一遍"：
def brute_match(text, pattern):
n, m = len(text), len(pattern)
for i in range(n - m + 1): # 每个可能的起点
j = 0
while j < m and text[i + j] == pattern[j]:
j += 1
if j == m: # 对完了，匹配成功
return i
return -1最坏情况（比如 text 全是 aaaaa，pattern 是 aaaab），每个起点都要比到最后一格才发现不匹配，复杂度 O(n×m)。
聪明办法：KMP 的核心直觉——"别白比了"
KMP（Knuth–Morris–Pratt）听起来吓人，但直觉特别朴素：
暴力匹配每次对不上，就把起点只往前挪一格，从头再来。可问题是——你刚刚比过的那些字符，信息全都浪费了。
举个例子，pattern 是 "abcab"，你在位置 4 发现 text 这里是 x，对不上。暴力办法下一步会退回起点+1，把 "abcab" 从头比。但请你睁大眼睛看："abcab" 的开头 "ab" 和结尾 "ab" 是一模一样的。
这意味着：你刚才已经比过的最后两个字符 "ab"，正好可以当成下一次匹配的开头！所以不用从头比，直接从第三个字符继续比就行。
这个"开头和结尾一样长"的东西，叫最长公共前后缀。KMP 干的事就一句话：
提前算好 pattern 每个位置"能回退到哪"，匹配失败时不从头来，而是跳到那个位置继续，保证已经比过的地方绝不再比第二遍。
这样，text 里的每个字符最多被比一次，复杂度降到 O(n + m)。
def kmp_search(text, pattern):
# 1) 先算 pattern 的 next 数组（每个位置失败后跳哪）
m = len(pattern)
nxt = [0] * m
k = 0
for i in range(1, m):
while k > 0 and pattern[i] != pattern[k]:
k = nxt[k - 1]
if pattern[i] == pattern[k]:
k += 1
nxt[i] = k
# 2) 拿着 next 去匹配 text
j = 0
for i in range(len(text)):
while j > 0 and text[i] != pattern[j]:
j = nxt[j - 1] # 关键：不回退到 0，跳到 nxt
if text[i] == pattern[j]:
j += 1
if j == m: # 匹配成功
return i - m + 1
return -1
print(kmp_search("ababcabcab", "abcab")) # 2
print(brute_match("ababcabcab", "abcab")) # 2别被 next 数组吓到，你现在只需要记住那个直觉："pattern 的开头结尾如果有重复，失败时就别从头比，跳到重复的地方接着比。" 面试真被问 KMP，能讲清这个直觉，已经赢了一半。
五、两个面试高频套路：回文 + 滑动窗口
套路一：判断回文（正着读倒着读一样）
def is_palindrome(s):
return s == s[::-1] # 切片反转，一行搞定
print(is_palindrome("abba")) # True
print(is_palindrome("abcba")) # True
print(is_palindrome("abc")) # False那"最长回文子串"呢？暴力是 O(n³)。优化思路：中心扩展——以每个字符（和每两个字符之间）为中心，向两边扩散，扩不动为止。O(n²)：
def longest_palindrome(s):
best = ""
for i in range(len(s)):
# 奇数长度中心（一个字符）
l = r = i
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
if r - l - 1 > len(best):
best = s[l + 1:r]
# 偶数长度中心（两个字符之间）
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
if r - l - 1 > len(best):
best = s[l + 1:r]
return best
print(longest_palindrome("babad")) # 'bab' 或 'aba'记住这个思想：回文是"中心对称"的，所以从中心往外扩，比从左往右硬扫聪明得多。
套路二：滑动窗口（无重复字符的最长子串）
经典题：给一个字符串，找出不含重复字符的最长子串的长度。
暴力是 O(n³)。聪明办法：双指针 + 集合，维护一个"窗口"，右指针不停往右扩，遇到重复就把左指针往右收，始终保证窗口内无重复。每个字符最多进出窗口一次，O(n)：
def length_of_longest_substring(s):
seen = set() # 窗口里现在有哪些字符
left = 0
best = 0
for right in range(len(s)):
while s[right] in seen: # 有重复，收左边界
seen.remove(s[left])
left += 1
seen.add(s[right]) # 加入新字符
best = max(best, right - left + 1)
return best
print(length_of_longest_substring("abcabcbb")) # 3（"abc"）
print(length_of_longest_substring("bbbbb")) # 1（"b"）滑动窗口的心法：凡是"连续子串/子数组"里求最长/最短/满足某条件，先想"左右两个指针框一个窗口"，右扩、左收，配合一个集合或字典记账。这是字符串和数组题的万能套路。
六、复杂度小结
| 操作 | 复杂度 | 说明 |
|---|---|---|
按下标取字符 s[i] | O(1) | 直接定位 |
切片 s[a:b] | O(b-a) | 要复制出一段，长度成正比 |
查找子串 in / find | O(n) | 内部要扫一遍 |
拼接 join | O(n) | 一次拼好，最快 |
拼接 += | O(n²) | 每次复制，别用 |
| 暴力匹配 | O(n×m) | 最坏 |
| KMP 匹配 | O(n+m) | 每个字符最多比一次 |
| 滑动窗口 | O(n) | 每个字符进出一次 |
七、字典树 Trie：前缀匹配的利器
前面我们玩字符串，都是"整串比较"。但有一类问题，整串比较很浪费：
输入法打"app"，要联想出 apple、application、appointment……这些词都有公共前缀"app"。
如果你有 10 万个单词，每输入一个字母都要扫一遍 10 万词，太慢。字典树（Trie） 就是为此而生：把单词按"字符"拆开，公共前缀只存一次。
结构：一棵按字符分叉的树
每个节点代表"一个字符"，从根走到某个节点，沿途字符拼起来就是一个前缀。
class Trie:
def __init__(self):
self.children = {}
self.is_end = False # 标记"这里是一个完整单词的结尾"
def insert(self, word):
node = self
for c in word:
node = node.children.setdefault(c, Trie())
node.is_end = True
def search(self, word): # 完整匹配
node = self
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_end
def starts_with(self, prefix): # 前缀匹配
node = self
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
t = Trie()
for w in ["cat", "car", "dog", "cart"]:
t.insert(w)
print(t.search("cat")) # True
print(t.search("ca")) # False（ca 是前缀，但不是完整单词）
print(t.starts_with("ca")) # True（有 ca 开头的单词）复杂度：只和"单词长度"有关，和"单词总数"无关
插入、查找、前缀匹配都是 O(L)，L 是单词长度——跟字典里有多少个词没关系。这是 Trie 相对哈希表的最大优势：哈希表查"精确匹配"很快，但没法高效回答"有没有 app 开头的词"，Trie 天生就会。
用在哪儿
| 场景 | 用法 |
|---|---|
| 输入法联想 | 按前缀"app"找到所有 app 开头的候选 |
| 拼写检查 | 快速判断一个词是否在词库 |
| IP 路由 | 最长前缀匹配（路由器查表） |
| 自动补全 | IDE、搜索引擎的补全 |
记住：Trie = 把"字符串"变成"树"，让"前缀匹配"从 O(n) 扫描变成 O(长度) 直达。
八、动手时间 🎯
实验 1：亲眼看看 += 和 join 差多少
import time
n = 100000
start = time.time()
s = ""
for i in range(n):
s += "x"
print("+= 拼接耗时:", round(time.time() - start, 3), "秒")
start = time.time()
s = "".join("x" for _ in range(n))
print("join 拼接耗时:", round(time.time() - start, 3), "秒")你大概率会看到 join 快几十上百倍。 这就是"不可变 + 反复复制"的代价。
实验 2：切片玩出花样
s = "0123456789"
print(s[::-1]) # 反转
print(s[::2]) # 取偶数下标
print(s[1::2]) # 取奇数下标
print(s[-3:]) # 最后三个
print(s[3:8:2]) # 从 3 到 8，隔一个取实验 3：写一个"统计词频 Top 3"（复习哈希表 + 字符串）
from collections import Counter
text = "the quick brown fox jumps over the lazy dog the fox"
c = Counter(text.lower().split())
print(c.most_common(3)) # [('the', 2), ('fox', 2), ...]实验 4（挑战）：最长公共前缀
给一堆字符串，求它们的最长公共前缀，比如 ["flower","flow","flight"] → "fl"。
def longest_common_prefix(strs):
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
while not s.startswith(prefix):
prefix = prefix[:-1] # 前缀砍掉最后一格，直到匹配
if not prefix:
return ""
return prefix
print(longest_common_prefix(["flower", "flow", "flight"])) # 'fl'九、小结
- 字符串不可变——"改"其实是"新建"，所以拼接用
join别用+=，切片是复制、随便切都安全。 - KMP 的直觉是"别白比了"——提前算好 pattern 的开头结尾重复，失败时跳到重复处继续，每个字符最多比一次。
- 滑动窗口是字符串题的万能套路——左右双指针框窗口、右扩左收、配集合或字典记账，把暴力 O(n²) 砍成 O(n)。
先别急着往后翻，把"回文中心扩展"和"无重复最长子串"敲熟，字符串的手感就长在你脑子里了。