String 解法总结
- 字符串的题目难度上升时，会包含几种方法的结合使用，还考察对代码的掌控能力。
双指针法
- 能对数组使用，那也能对字符串使用，因为字符串本质是一个字符数组
首尾指针
- 把双指针设在字符串（数组）的首尾，在保存两个字符后，可以做比较，交换的操作
- 交换（反转）
- 想实现反转字符串，我们常用首尾指针，并交换首尾字符。
- 进一步的，我们可以限定首尾的位置，也就是限定反转的字符范围
- 题目：
- 344.反转字符串 最简单的首尾指针应用
- 541.反转字符串 II，考察了 for 循环里 i 值的灵活设置
- 151.翻转字符串里的单词 ，要限定反转的字符范围
- 剑指 Offer 58 - II.左旋转字符串，灵活使用反转：整体反转 + 局部反转
快慢指针
- 本质是快指针决定慢指针的操作
- 比如，我们要移除空格，我们可以在快指针不遇到空格时，把快指针指向的值赋给慢指针，遇到时，就不赋值。实现慢指针填充的数组里没有空格。这里我们在不同情况，让快指针决定给不给慢指针赋值
- 题目
- 151.翻转字符串里的单词的 移除多余空格
- 沿用我们移除数组元素的思路，我们把要移除的数组元素视为空格
- 快指针遇到空格就跳过，不把空格赋给慢指针
- 此处给单词之间加空格，也考察了对代码的掌控能力，我们要判断好什么时候遍历完一个单词
- 剑指 Offer 05.替换空格
- 此题快慢指针使用了倒序遍历的方式
- 快指针遇到空格时，此时快指针不赋值，快指针决定让慢指针去填充
20%的赋值。
- 151.翻转字符串里的单词的 移除多余空格
KMP
- KMP 可用来找之前匹配过的字符串的位置
- KMP 有一个 next 数组，里面记录了各种相等的前后缀长度，里面的的最长相等前后缀长度是我们需要的。借此，我们可以找到已经匹配过的位置
- 题目
- 匹配问题：28. 实现 strStr()
- 在处理不匹配的问题上，
j=next[x]的使用- 在构建 next 数组的构建过程中，前后缀不匹配时，我们通过已构建的 next 数组，重新设置前缀末尾的位置。
j=next[x] - 在文本串和模式串的匹配过程中，文本串模式串不匹配时，我们通过得到的 next 数组，重新设置了指向模式串的指针
j=next[x]
- 在构建 next 数组的构建过程中，前后缀不匹配时，我们通过已构建的 next 数组，重新设置前缀末尾的位置。
- 在处理不匹配的问题上，
- 重复子串问题：459.重复的子字符串
- 在原串有重复的子字符串时，原串的长度与 KMP 的最长相等前后缀长度 差值为 一个重复子串的长度。借此我们可以用取余来看，原串是否有重复的子字符串
- 具体代码：
if (next[len - 1] > 0 && len % (len - next[len - 1]) == 0)(next 数组直接使用前缀表)
- 匹配问题：28. 实现 strStr()
参考：代码随想录-字符串总结