简述
写在前面的话
就我个人而言, 我其实是不想要单独写一章字符串的学习笔记的, 因为字符串作为数据结构能说的全都在数组篇前面的章节中说完了, 而字符串相关的算法又非常畸形。 所谓畸形就是指处理字符串的算法难度分布非常不均匀, 普遍都是初级和中级偏简单的算法, 这些和数组也是高度重合的, 而偏偏最难的KMP算法又是高阶算法里比较难的, 光是思考如何归类这篇笔记归都已经让我纠结了, 最后索性作为数组篇的番外写了。
虽然字符串这篇笔记在我看来可有可无, 但是请千万不要忽视字符串在面试中的重要性, 一个简单的统计供大家参考:
在我写这篇笔记的时候, LeetCode上最多的题目是数组, 共有1958道, 第二多的就是字符串, 共有819道。
可见数组和字符串在面试和笔试中的重要性。毕竟如果面试题中如果给你两道算法, 会有超过80%的概率两道题中能够碰到至少一个数组和字符串有关的题。
字符串基础
字符串的定义:
"字符串是若干字符组成的有限序列，也可以理解为是一个字符数组。"
很多语言也确实是用数组来实现字符串的。 以C语言为例, 字符串就是一个char的数组, 最后以结束字符'\0'来表示字符串结束, 这种实现普遍存在于各种编程语言。
很多语言中也同时存在字符数组和字符串两种数据结构, 比如Java的string和char[]。初学者可能并不清楚两者是否有什么区别, 因为 严格意义上讲, 在基本操作上没有区别, 但是string作为数据类型会提供更多处理字符串的接口, 这些是char[]没有的。
相比于char array, 字符串作为内置数据结构也可能存在更多的限制, 以Python为例, 如果我想修改自字符串中的某个char, 是无法直接通过索引向该位置赋值的, 因为Python中字符串是不可变对象。
# Python 字符串不可变
s = "Hello World"
s[6] = "w" # Error
# 正确做法
s = s[:6] + "w" + s[7:]
字符串问题类型
字符串的问题千奇百怪, 按照问题分类不太现实, 尤其是LeetCode序号超过2000以后的题目, 特别喜欢新瓶装旧酒, 也就是一些老的问题套上一个新的问题背景, 有的甚至会配上一大段的背景知识。
但是从「解题算法」的角度出发, 字符串的问题基本上可以分为四大类。
第一类: 送分题 - 模拟类问题
这类问题普遍是简单题, 通常就是题干中描述一个场景, 或者规定一种计算方式, 让你根据已知的字符串求一个值或者找一个/一组字符串中的字符。
普遍解法就是: 模拟 (无非就是暴力搜索 + 枚举)
例题: LeetCode #13 罗马数字转整数
第二类: 基础题 - 字符串反转
单纯的反转字符串很简单, 但是反转的基础上也经常会被加一些玩法, 这时候就考验代码掌控力了, 虽然难度一般最多也就普通, 但面试时很容易翻车, 因为部分代码很考验基础(边界判断/条件控制)。
一道比较典型的例题是 LeetCode #541 反转字符串II
这是个典型的分段反转问题, 也叫做「局部反转」, 不再无脑反转整个字符串, 而是需要按照固定规律一段一段处理字符串。虽然难度还是不高, 但是很容易写得冗余, 一堆逻辑代码和计数器来统计。
其实分段处理字符串的技巧就是要想办法在for循环的表达式上做文章, 虽然降低不了开销, 但是可以简化代码。
还有一道偏综合的例题 LeetCode #151 翻转字符串里的单词
这题很经典, 因为包含了多种字符串操作, 当然这是不考虑使用.split()函数的情况, 否则用内置字符串接口 + 用O(N)的辅助空间这道题未免太水了。
如果必须在原字符串上操作, 那就会很有意思, 无脑反转的话单词同样会被反转, 所以有一种做法就是「整体反转 + 局部反转」, 先无脑整个字符串反转后, 用双指针。 左右指针分别在遍历中标记一个单词的开头和结尾, 确定一个单词的左右边界后开始首尾交换, 然后再跳过空格开始找下一个单词。
第三类: 高频题 - 双指针系列
毫无疑问的是, 双指针在数组, 链表和字符串中是最常用的算法。核心思想就是用两个指针在O(n)的时间完成一个指针O(n^2)的遍历
上一个例题也使用了双指针, 但并不算最典型的双指针题型, 因为双指针在整个算法中只是工具, 「整体反转 + 局部反转」的解题思想才是题目的精髓。
我个人而言非常重视双指针这个算法, 因为面试中出现极大概率能够用到, 而且应用非常广, 无论是放在数组还是链表的章节讲双指针都有些不妥。于是我决定单独开一篇笔记, 专门记录我对双指针算法的理解。
第四类: 送命题 - KMP算法系列
KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
之所以双指针有资格单开一章节, 而KMP这种高阶算法只能沦落到在数组篇的番外讲, 是因为KMP的精髓是「前缀表」。这个思想和《数组篇·前缀和》有一定相似之处, 紧接着前缀和的章节或许对于理解有一定帮助, 此外, 不同于双指针, KMP算法基本上没有可能用到除字符串以外的题目中。
KMP算法精讲🌟
KMP算法对于很多人来说一直是一种熟悉又陌生的算法。作为处理字符串相关的算法, KMP算法应该是很多学习者在学习算法的初期就会接触到的第一个高阶算法, 恐怕也是很多学习者第一个被难度强行劝退的高级算法。
顺便补充一下, 我最开始学习的时候非常好奇KMP算法的名字到底什么意思, 查完资料发现没啥深意，就是发明这个算法的三位学者名字首字母合起来。
因为考察频率极低, 所以很多人都不乐意花时间和精力去学习KMP算法, 我即将毕业准备找工作的时候也是如此认为的。但是后来了解过KMP算法之后才会发现, 虽然KMP算法很难理解, 但是它在用一种很优雅的方式优化了字符串匹配的方式, 这么看来花点时间学习和思考这个算法只不过是微不足道的小代价。我相信每一个算法学习者在第一次领悟KMP算法精髓的时候都会由衷地感谢和赞美发明KMP算法的三位学者。
KMP到底能解决什么样的问题?
前文其实已经剧透了不止一次了, KMP是专门用来解决「字符串匹配问题」的算法。
首先, 「字符串匹配」问题是比较常见的问题, 但是它的解法除了暴力破解, 基本上就是KMP算法, 属于是「优雅和暴力的两个极端」二选一, 很显然大多数人选择的都是暴力破解。 但是使用暴力破解最怕的就是看到题目背景中字符串的最大长度太长, 高复杂度的解法基本上注定要timeout。那么这种题就已经约等于「非KMP勿扰」了。
作为一个算法学习者, 如果让我们来优化字符串匹配的问题, 第一直觉肯定是从「缩小搜索空间」的角度来优化, 但是会发现无论是用滑动窗口还是用队列来试图匹配「标准子字符串」时, 都会遇到一个问题:
那就是「当某个子字符串不匹配时, 往右移动窗口时, 需要从头对比整个子字符串」。
很多敏锐一点的学习者可以意识到这个操作浪费了太多的性能做无意义的搜索, 但是又无可奈何, 因为实在是想不出来有什么办法可以让「死板的算法自己去判断子字符串的哪些部分是值得搜索的」。所以只能暴力破解。
而KMP之所以优雅, 就是因为「当字符串不匹配时, 它可以有效利用已经匹配过的文本内容, 避免从头再去做匹配」。
所以说, 优化的方向大家都明白, 但是只有KMP这三位学者想到了一个办法真正做到了这一点, 成为了第一个「线性时间的字符串匹配算法」。只此一点, KMP算法就足以称之为宗师之作。
工作原理 - 「前缀表」
线性的字符串匹配算法, 凭什么KMP能够做到? 这个算法是如何利用之前已经匹配过的子串的? 这个记录是都是在什么时候更新的?
上世纪70年代, 在大多数人苦恼怎么通过剪枝的方式减少搜索空间时, 只有KMP三人想到了利用「最长相等前后缀」的方式来记录可以可以重复利用的字符串内容。