30 秒速览
- 什么时候用：文本匹配、回文判断、字符串模拟、字符统计
- 核心技法：双指针、中心扩展、KMP、滑动窗口
- Python 技巧：切片、join、Counter
- 常见陷阱：字符串不可变、频繁拼接性能差
一、直觉建立
字符串的特殊性
字符串本质上是字符数组，但有其特点：
- 不可变性：Python 中字符串不可变，每次"修改"都创建新对象
- 有序性：字符顺序很重要，“abc” != “bac”
- 可比较：字典序比较，“apple” < “banana”
字符串问题分类
| 类型 | 典型题目 | 核心技法 |
|---|---|---|
| 匹配问题 | strStr()、正则匹配 | KMP、双指针 |
| 回文问题 | 最长回文子串 | 中心扩展、DP |
| 变位词 | 字母异位词分组 | 排序/计数 |
| 子串问题 | 最小覆盖子串 | 滑动窗口 |
| 模拟运算 | 字符串相加/相乘 | 模拟竖式 |
二、核心技法
1. 字符串切片
s = "hello world"
# 基本切片
s[0:5] # "hello"
s[6:] # "world"
s[::-1] # "dlrow olleh"（反转）
# 每隔 k 个取一个
s[::2] # "hlowrd"
# 删除首尾字符
s[1:-1] # "ello worl"
2. 高效拼接
# 错误：O(n²) 复杂度
result = ""
for s in strings:
result += s # 每次都创建新字符串
# 正确：O(n) 复杂度
result = "".join(strings)
3. 字符统计
from collections import Counter
# 统计字符频率
count = Counter("hello")
# Counter({'l': 2, 'h': 1, 'e': 1, 'o': 1})
# 判断变位词
def isAnagram(s: str, t: str) -> bool:
return Counter(s) == Counter(t)
三、典型例题
例题 1：LC 344. 反转字符串
题目：原地反转字符串（用列表表示）。
思路
双指针，首尾交换。
def reverseString(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
复杂度：时间 O(n)，空间 O(1)
例题 2：LC 5. 最长回文子串
题目：给你一个字符串 s，找到 s 中最长的回文子串。
示例：
输入：s = "babad"
输出："bab"（或 "aba"）
中心扩展法
回文串关于中心对称，可以从中心向两边扩展。
def longestPalindrome(s: str) -> str:
if not s:
return ""
def expand(left: int, right: int) -> str:
# 从中心向两边扩展
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# 返回找到的回文串
return s[left + 1:right]
result = ""
for i in range(len(s)):
# 奇数长度回文（单中心）
odd = expand(i, i)
# 偶数长度回文（双中心）
even = expand(i, i + 1)
# 更新最长
if len(odd) > len(result):
result = odd
if len(even) > len(result):
result = even
return result
为什么中心扩展有效？
- 回文串是对称的
- 中心只有 O(n) 个（n 个单中心 + n-1 个双中心）
- 每个中心最多扩展 O(n) 次
复杂度：时间 O(n²)，空间 O(1)
例题 3：LC 415. 字符串相加
题目：给定两个字符串形式的非负整数，返回它们的和（字符串形式）。
示例：
输入：num1 = "11", num2 = "123"
输出："134"
模拟竖式加法
def addStrings(num1: str, num2: str) -> str:
i, j = len(num1) - 1, len(num2) - 1
carry = 0
result = []
while i >= 0 or j >= 0 or carry:
n1 = int(num1[i]) if i >= 0 else 0
n2 = int(num2[j]) if j >= 0 else 0
total = n1 + n2 + carry
carry = total // 10
result.append(str(total % 10))
i -= 1
j -= 1
return "".join(reversed(result))
复杂度：时间 O(max(m,n))，空间 O(max(m,n))
例题 4：LC 43. 字符串相乘
题目：给定两个以字符串形式表示的非负整数，返回它们的乘积。
思路
模拟竖式乘法，但可以用数组优化。
def multiply(num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
m, n = len(num1), len(num2)
# 结果最多 m + n 位
result = [0] * (m + n)
# 从右到左逐位相乘
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
mul = int(num1[i]) * int(num2[j])
# 位置
p1, p2 = i + j, i + j + 1
# 叠加到 result
total = mul + result[p2]
result[p2] = total % 10
result[p1] += total // 10
# 转为字符串，跳过前导零
s = "".join(str(x) for x in result)
return s.lstrip("0")
关键点：
num1[i] * num2[j]的结果放在i+j和i+j+1位置- 用数组存储中间结果，最后统一处理进位
复杂度：时间 O(mn)，空间 O(m+n)
例题 5：LC 49. 字母异位词分组
题目：给定一个字符串数组，将字母异位词分组。
示例：
输入：strs = ["eat","tea","tan","ate","nat","bat"]
输出：[["bat"],["nat","tan"],["ate","eat","tea"]]
方法一：排序作为 key
from collections import defaultdict
def groupAnagrams(strs: list[str]) -> list[list[str]]:
groups = defaultdict(list)
for s in strs:
# 排序后作为 key
key = "".join(sorted(s))
groups[key].append(s)
return list(groups.values())
复杂度：时间 O(n × k log k)，k 是字符串最大长度
方法二：计数作为 key
def groupAnagrams(strs: list[str]) -> list[list[str]]:
groups = defaultdict(list)
for s in strs:
# 计数作为 key（26 个字母）
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
key = tuple(count)
groups[key].append(s)
return list(groups.values())
复杂度：时间 O(n × k)，空间 O(n × 26)
例题 6：LC 28. 找出字符串中第一个匹配项
题目：在 haystack 中找出 needle 的第一个匹配位置，返回下标。
朴素匹配
def strStr(haystack: str, needle: str) -> int:
if not needle:
return 0
n, m = len(haystack), len(needle)
for i in range(n - m + 1):
if haystack[i:i+m] == needle:
return i
return -1
复杂度：时间 O(n × m)
KMP 算法
KMP 利用已匹配信息，避免从头开始。
def strStr(haystack: str, needle: str) -> int:
if not needle:
return 0
# 构建 next 数组
def build_next(pattern: str) -> list[int]:
m = len(pattern)
next_arr = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = next_arr[j - 1]
if pattern[i] == pattern[j]:
j += 1
next_arr[i] = j
return next_arr
next_arr = build_next(needle)
j = 0
for i in range(len(haystack)):
while j > 0 and haystack[i] != needle[j]:
j = next_arr[j - 1]
if haystack[i] == needle[j]:
j += 1
if j == len(needle):
return i - j + 1
return -1
next 数组含义：next[i] 表示 pattern[0:i+1] 的最长相同前后缀长度。
复杂度：时间 O(n + m)，空间 O(m)
例题 7：LC 3. 无重复字符的最长子串
题目：给定一个字符串，找出不含有重复字符的最长子串的长度。
滑动窗口
def lengthOfLongestSubstring(s: str) -> int:
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
# 收缩窗口直到无重复
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
复杂度：时间 O(n)，空间 O(min(m, n))，m 是字符集大小
四、字符串问题判断流程
字符串问题
├── 匹配/查找
│ ├── 简单匹配 → 暴力/双指针
│ └── 多次匹配 → KMP
│
├── 回文
│ ├── 单个回文 → 中心扩展
│ └── 所有回文 → Manacher / DP
│
├── 子串/子序列
│ ├── 无重复 → 滑动窗口
│ └── 最长公共 → DP
│
├── 变位词
│ ├── 排序后作为 key
│ └── 计数作为 key
│
└── 模拟运算
└── 从低位到高位处理
五、常见错误与陷阱
错误 1：频繁字符串拼接
# 错误：O(n²)
result = ""
for c in chars:
result += c
# 正确：O(n)
result = "".join(chars)
错误 2：KMP next 数组构建错误
# next[i] 是 pattern[0:i+1] 的最长相等前后缀长度
# 不是 pattern[0:i] 的
错误 3：回文中心遗漏
# 中心扩展要考虑两种情况：
# 1. 奇数长度：单中心 (i, i)
# 2. 偶数长度：双中心 (i, i+1)
错误 4：字符串越界
# 切片不会越界，但索引会
s = "abc"
s[5] # IndexError
s[5:10] # ""（空字符串，不报错）
六、复盘清单
触发信号
- 字符串匹配/查找
- 回文判断
- 变位词/重排
- 子串/子序列
- 大数运算
技法选择
- 简单匹配 → 双指针
- 高效匹配 → KMP
- 回文问题 → 中心扩展
- 无重复子串 → 滑动窗口
- 变位词 → 排序/计数分组
边界条件
- 空字符串
- 单字符
- 所有字符相同
- Unicode 字符
七、题目清单
基础题
| 题号 | 题目 | 难度 | 考点 |
|---|---|---|---|
| 344 | 反转字符串 | Easy | 双指针 |
| 541 | 反转字符串 II | Easy | 分段处理 |
| 415 | 字符串相加 | Easy | 模拟 |
| 49 | 字母异位词分组 | Medium | 哈希分组 |
进阶题
| 题号 | 题目 | 难度 | 考点 |
|---|---|---|---|
| 5 | 最长回文子串 | Medium | 中心扩展 |
| 43 | 字符串相乘 | Medium | 模拟乘法 |
| 28 | 实现 strStr() | Medium | KMP |
| 3 | 无重复最长子串 | Medium | 滑动窗口 |
| 76 | 最小覆盖子串 | Hard | 滑动窗口 |
| 72 | 编辑距离 | Hard | DP |