字符串操作题几乎出现在每场编程面试中。它考察你对字符级操作的掌握、对哈希表的高效使用,以及处理空字符串、Unicode、大小写等边界情况的能力。
回文:用双指针从两端向中间移动,逐对比较字符。O(n) 时间,O(1) 空间。
变位词:排序两个字符串后比较,或用频率计数哈希表达到 O(n) 时间。
最长无重复子串:用滑动窗口加哈希集合,跟踪当前窗口中的字符。
始终讨论边界情况:空字符串、单字符、Unicode、大小写敏感性。
检查回文时,我用双指针从首尾字符向中间移动,若所有字符对匹配则是回文——O(n) 时间,O(1) 空间。检测变位词时,我为第一个字符串建频率表,再用第二个字符串递减计数,所有计数为零则是变位词——O(n) 时间,O(k) 空间,k 为字母表大小。求最长无重复字符子串时,我用滑动窗口加哈希集合,右指针扩展窗口并加入字符,遇到重复时从左端收缩窗口直到重复移除,过程中记录最大窗口长度。时间 O(n),空间 O(min(n,m)),m 为字符集大小。我总会确认是否需要处理 Unicode、空格或不区分大小写。
滑动窗口是子串问题的首选模式——一定要熟练掌握。
编码前确认大小写敏感性和字符集(ASCII 还是 Unicode)。
注意字符串不可变性——在 Java/Python 中循环拼接是 O(n²),应用 StringBuilder 或列表 join。
滑动窗口用两个指针维护数组或字符串中的动态范围,通过扩展和收缩高效满足约束条件。
使用语言自带的 Unicode 方法。Python 字符串默认支持 Unicode。Java 中对增补字符应使用 codePoints() 而非 charAt()。
概念相似,但双指针回文检查更高效,不匹配时可提前退出,无需创建反转副本。