几道常见的字符串算法题
字符串可视为字符序列,但工程上必须先确认字符模型:按字节、Unicode 码点还是用户看到的字素处理。纯 ASCII 题可用定长频次数组,字符集不确定时更适合哈希表,不能默认一个 char 就等于一个完整字符。
常见模型有四类。字符计数用于异位词和首次唯一字符;双指针适合回文、反转与有序字符串;滑动窗口维护连续子串的约束;模式匹配则关注如何避免主串指针反复回退。朴素匹配最坏 O(nm),KMP 通过模式串的前缀信息,在失配时复用已知匹配,预处理与搜索合计 O(n+m)。
回文判断可从两端向中间走,忽略规则外字符后比较;最长回文子串可从每个中心向两侧扩展,时间 O(n²)、空间 O(1)。无重复最长子串用窗口记录字符最后位置,右端加入重复字符时,把左端跳到旧位置之后,整体 O(n)。
字符串拼接也有实践成本。循环中反复创建不可变字符串可能产生二次方复制,应使用可变缓冲区。哈希统计的空间是 O(字符集大小),字符集固定时可视为常数,但表达时最好说明前提。
误区包括混淆子串与子序列、窗口收缩后忘记更新计数、Unicode 处理不当、KMP 前缀表定义前后不一致,以及使用切片导致隐藏复制。小结:先明确连续性、字符范围与所需操作,再选择计数、指针、窗口或前缀匹配机制。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Dai Wei!
评论

