字符串算法进阶总结 | 滑动窗口、回文与匹配

引言

字符串算法是面试中的重要主题。本文总结字符串算法中的核心技巧，包括滑动窗口、回文检测和字符串匹配。

滑动窗口

滑动窗口是处理子串问题的有效方法。核心思想是维护一个可变大小的窗口，通过移动左右指针来扩展或收缩窗口。

典型问题

1. 无重复字符的最长子串：使用哈希表记录字符位置
2. 最小覆盖子串：同时维护两个计数表
3. 字母异位词：固定窗口大小的滑动窗口

模板

def slidingWindow(s, t): window = {} need = Counter(t) left, right = 0, 0 valid = 0 while right < len(s): c = s[right] right += 1 # 更新窗口 while valid == len(need): # 更新结果 d = s[left] left += 1 # 收缩窗口

回文检测

中心扩展法

def expandAroundCenter(s, left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left + 1:right]

动态规划

dp[i][j] = True if s[i] == s[j] and (j - i < 3 or dp[i+1][j-1])

字符串匹配

KMP 算法

KMP 算法通过预处理模式串，构建最长前缀后缀数组（ LPS），避免重复匹配。

动态规划

正则表达式和通配符匹配使用动态规划，通过状态转移方程求解。

常见技巧

哈希表统计

使用 Counter 或字典统计字符出现次数。

双指针

两端向中间移动或同向移动。

预处理

排序、统计、构建辅助数据结构。

面试常见问题

1. 如何处理字符集很大的情况？使用字符映射或 Unicode 编码。
2. 如何优化空间复杂度？使用数组代替哈希表。
3. 如何处理边界情况？空字符串、单个字符、全相同字符。

总结

字符串算法需要掌握滑动窗口、回文检测和字符串匹配的核心技巧。多练习典型问题，可以提高解决字符串相关问题的能力。