字符串算法进阶总结 | 滑动窗口、回文与匹配
字符串算法进阶总结 | 滑动窗口、回文与匹配
引言
字符串算法是面试中的重要主题。本文总结字符串算法中的核心技巧，包括滑动窗口、回文检测和字符串匹配。
滑动窗口
滑动窗口是处理子串问题的有效方法。核心思想是维护一个可变大小的窗口，通过移动左右指针来扩展或收缩窗口。
典型问题
- 无重复字符的最长子串：使用哈希表记录字符位置
- 最小覆盖子串：同时维护两个计数表
- 字母异位词：固定窗口大小的滑动窗口
模板
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 或字典统计字符出现次数。
双指针
两端向中间移动或同向移动。
预处理
排序、统计、构建辅助数据结构。
面试常见问题
- 如何处理字符集很大的情况？使用字符映射或 Unicode 编码。
- 如何优化空间复杂度？使用数组代替哈希表。
- 如何处理边界情况？空字符串、单个字符、全相同字符。
总结
字符串算法需要掌握滑动窗口、回文检测和字符串匹配的核心技巧。多练习典型问题，可以提高解决字符串相关问题的能力。