字符串 解题模板

适用场景

字符串匹配、子串操作、字符统计、格式转换

通用模板

双指针（回文 / 反转）

 
# 验证回文
 
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
 

KMP（字符串匹配）

 
# 构建 next 数组
 
def build_next(pattern):
 
    next_arr = [0] * len(pattern)
 
    j = 0
 
    for i in range(1, len(pattern)):
 
        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
 

模拟竖式运算

 
# 字符串相加
 
i, j, carry = len(a)-1, len(b)-1, 0
 
res = []
 
while i >= 0 or j >= 0 or carry:
 
    n1 = int(a[i]) if i >= 0 else 0
 
    n2 = int(b[j]) if j >= 0 else 0
 
    total = n1 + n2 + carry
 
    carry = total // 10
 
    res.append(str(total % 10))
 
    i -= 1; j -= 1
 

复杂度总结

模式	时间	空间	典型题
双指针	O(n)	O(1)	回文串、反转单词
KMP	O(m+n)	O(m)	字符串匹配
滑动窗口	O(n)	O(k)	无重复子串、覆盖子串
模拟竖式	O(max(m,n))	O(max(m,n))	相加、相乘

→ 查看该分类题目：LeetCode学习路线图 > 二、字符串

---

关联题型

关联题型	常见结合方式	典型题目
滑动窗口	子串问题 + 窗口维护	3无重复字符最长子串
动态规划	字符串匹配、编辑距离	72编辑距离
数组与哈希	字符计数 + 哈希表	242有效字母异位词