代码随想录算法训练营第九天| 151.翻转字符串里的单词、右旋转字符串 、28. 实现 strStr()、459.重复的子字符串、字符串总结

151.翻转字符串里的单词

题目链接：151.翻转字符串里的单词
文档讲解：代码随想录翻转字符串里的单词
视频讲解：LeetCode：翻转字符串里的单词
状态：参考自己写出来的

思路：
反转：思路很清晰，首先删掉多余空格，然后反转字符串，最后反转单词，返回字符串。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

// 反转
class Solution {
public:void removeSpace(string& s) {int j = 0;//记录新字符串长度for (int i = 0; i < s.size(); ++i) {// 非空格情况if (s[i] != ' ') {// 主动加空格 跳过开头if (j != 0) s[j++] =' ';// 找到单词while (i < s.size() && s[i] != ' ') s[j++] = s[i++];}}// 更新字符串s.resize(j);}void reverse(string& s, int start, int end) {for (int i = start, j = end - 1; i < j; i++,j--) {swap(s[i], s[j]);}}string reverseWords(string s) {// 删除多余空格removeSpace(s);// 反转字符串reverse(s, 0, s.size());// 反转单词for (int i = 0, j = 0; i < s.size(); ++i) {while (i < s.size() && s[i] != ' ') i++;reverse(s, j, i);j = i + 1;}return s;}
};

卡码网：55.右旋转字符串

题目链接：55.右旋转字符串
文档讲解：代码随想录右旋转字符串
状态：自己写的

思路：
感觉字符翻转/旋转都是一个点，围绕这个点来回翻转就好了。
双指针：反转整个字符串，然后根据区域反转，先[0,k)，再[k,s.size())，最后输出字符串。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

// 双指针
#include <iostream>
#include <string>
using namespace std;
void reverse(string& s, int start, int end){for (int i = start, j = end - 1; i < j; i++, j--){swap(s[i], s[j]);}
}
int main() {int k;cin >> k;string s;cin >> s;// 反转整个字符串reverse(s, 0, s.size());// 分区域反转// n前reverse(s, 0, k);// n后reverse(s, k, s.size());cout << s << endl;return 0;
}

28. 找出字符串中第一个匹配项的下标

题目链接：28. 找出字符串中第一个匹配项的下标
文档讲解：代码随想录实现 strStr()
视频讲解：LeetCode：实现 strStr()
状态：学会了

思路：
KMP：（1）得到前缀和-next数组：数组右移，初始化数组，开始遍历模式串，如果前后缀不同，则指针j返回上一个位置，如果前后缀相同，则指针j向后移动，并记录前缀和（j）到next当前位置中。（2）总函数：首先判断模式串是否为空串（是的话返回0），定义next数组，并初始化前缀和指针，开始遍历文本串，如果不匹配，则指针返回匹配到的上一个位置，如果匹配，则指针后移，如果找到（完全匹配），则返回文本串下标减去模式串的长度，最后如果没找到，则返回-1。

• 时间复杂度：O(m + n)
• 空间复杂度：O(m)

// KMP
class Solution {
public:// 字符串匹配// 前缀和// 得到前缀和void getNext(int* next, const string& s) {// 数组右移int j = -1;next[0] = j;// 遍历模式串for (int i = 1; i < s.size(); i++) {// 前后缀不同 0while (j >= 0 && s[i] != s[j + 1]) j = next[j];// 前后缀相同if (s[i] == s[j + 1]) j++;next[i] = j;//前缀和存入}}int strStr(string haystack, string needle) {// 特殊：模式串为空if (needle.size() == 0) return 0;// 前缀和vector<int> next(needle.size());getNext(&next[0], needle);int j = -1;// 遍历文本串for (int i = 0; i < haystack.size(); i++) {// 不匹配 0while (j >= 0 && haystack[i] != needle[j + 1]) j = next[j];// 匹配if (haystack[i] == needle[j + 1]) j++;//i++;// 找到了if (j == needle.size() - 1) return (i - needle.size() + 1);}// 没有找到return -1;}
};

注意：
不匹配和前后缀不同，都要从非头（>=0）开始。
涉及到next数组不要忘记指针是从-1开始，需要初始化数组。
模式字符串为空串是一种特殊情况：当needle为空字符串时，可以将其看作是一种特殊的 “存在”，它在任何字符串中都可以视为从最开头（也就是位置0）就 “出现” 了，因为它不需要匹配任何实际字符内容，空字符串就像一个 “占位为无” 的元素，天然地处在目标字符串的开头起始处，所以返回0符合其作为起始位置的逻辑概念。

459.重复的子字符串

题目链接：459.重复的子字符串
文档讲解：代码随想录重复的子字符串
视频讲解：LeetCode：重复的子字符串
状态：

思路：

• 时间复杂度：
• 空间复杂度：

在这里插入代码片

字符串总结

定义：字符串是若干字符组成的有限序列，也可以理解为是一个字符数组，但是很多语言对字符串做了特殊的规定，接下来来说一说C/C++中的字符串。

• 在C语言中，把一个字符串存入一个数组时，也把结束符 '\0’存入数组，并以此作为该字符串是否结束的标志。
• 在C++中，提供一个string类，string类会提供 size接口，可以用来判断string类字符串是否结束，就不用’\0’来判断是否结束。
• 那么vector< char > 和 string 又有什么区别呢？其实在基本操作上没有区别，但是 string提供更多的字符串处理的相关接口，例如string重载了+，而vector却没有。所以想处理字符串，还是会定义一个string类型。
  经典：
• 双指针：双指针法在数组，链表和字符串中很常用。其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。 例题1 例题2 例题3 例题4
• 反转：当需要固定规律一段一段去处理字符串的时候，要想想在for循环的表达式上做做文章。整体反转，局部反转… 例题1 例题2 例题3
• KMP：KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头匹配。
  KMP的精髓就是前缀表。前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串。后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串。
  使用KMP可以解决两类经典问题：1.匹配问题 例题 2.重复子串问题 例题。
  针对前缀表到底要不要减一，这就是不同KMP实现方式，其中主要理解**j=next[x]**这一步最为关键。

双指针法是字符串处理的常客。

KMP算法是字符串查找最重要的算法。

KMP算法

• 什么是KMP
  有三位学者发明，取了三位名字的首字母，叫KMP。

• KMP有什么用
  主要用在字符串匹配上。**当字符出现不匹配的时候，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去匹配了。**所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

• 什么是前缀表
  next 数组就是一个前缀表（prefix table）。前缀表的作用是用来回退的，它记录了模式串与主串（文本串）不匹配的时候，模式串应该从哪里开始重新匹配。注意：是从文本串中查找是否出现过模式串。前缀表是记录下标i之前（包含i）的字符串中，有多大长度的相同前缀后缀。这里说的字符串前缀是不包含最后一个字符的所有以第一个字符开头的连续子串，后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。因为前缀表要求的是相同前后缀的长度。

• 为什么一定要用前缀表
  前缀表有告知当前位置匹配失败，跳到之前已经匹配的地方的能力。对于字符串"aabaa"来说最长相等的前缀 和 后缀字符串是 子字符串aa，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀字串的后面，那么我们找到与其相同的前缀的后面重新匹配就好了。
  

• 如何计算前缀表
  模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。这样就知道前面字符串的最长相同的前缀和后缀，就可以找到下标，移动到那里后继续比较。

• 前缀表与next数组
  很多KMP算法的实现都是通过next数组来做回退操作的。next数组 就可以是前缀表，但很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。这样处理并不涉及到KMP具体原理，而是具体实现，next数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。

• 使用next数组来匹配
  用前缀表统一减一之后的next数组来做演示。

• 时间复杂度分析
  单独生成next数组，时间复杂度是O(m)。匹配字符串的时间是O(m)。所以时间复杂度就i是O(m+n)。

• 构造next数组
  定义一个函数getNext来构建next数组，函数参数为指向next数组的指针，和一个字符串。构造next数组其实就是计算模式串s，前缀表的过程。主要分为以下三步：
  1.初始化 ：定义两个指针，int j=-1;next[0]=j;
  2.处理前后缀不相同的情况：遍历模式串s的时候，从1开始，s[i]与s[j+1]不相同（前后缀末尾不相同），就要向前退，就要找j+1前一个元素在next数组里面的值（next[j]）。
  3.处理前后缀相同的情况：如果s[i]与s[j+1]相同，那么同时向后移动i和j，说明找到了相同的前后缀，同时还要将j(前缀长度）赋给next[i]，因为next[i]要记录相同前后缀的长度。

void getNext(int* next, const string& s){int j = -1;next[0] = j;for(int i = 1; i < s.size(); i++) { // 注意i从1开始while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了j = next[j]; // 向前回退}if (s[i] == s[j + 1]) { // 找到相同的前后缀j++;}next[i] = j; // 将j（前缀的长度）赋给next[i]}
}

• 使用next数组来做匹配？
  在文本串s里找是否出现过模式串t。定义两个下标：j指向模式串起始位置，i指向文本串起始位置。遍历文本串s，比较s[i]与t[j+1]进行比较。如果不相同，j就要从next数组里寻找下一个匹配的位置。如果相同，则i和j同时向后移动。如果j指向了模式串t的末尾，那么说明模式串t完全匹配文本串s里的某个字串。
  对于本道题要找到模式串的第一个位置（从0开始），所以返回当前在文本串匹配模式串的位置i减去模式串的长度。

int j = -1; // 因为next数组里记录的起始位置为-1
for (int i = 0; i < s.size(); i++) { // 注意i就从0开始while(j >= 0 && s[i] != t[j + 1]) { // 不匹配j = next[j]; // j 寻找之前匹配的位置}if (s[i] == t[j + 1]) { // 匹配，j和i同时向后移动j++; // i的增加在for循环里}if (j == (t.size() - 1) ) { // 文本串s里出现了模式串treturn (i - t.size() + 1);}
}

• 前缀表统一减一 C++代码实现

class Solution {
public:void getNext(int* next, const string& s) {int j = -1;next[0] = j;for(int i = 1; i < s.size(); i++) { // 注意i从1开始while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了j = next[j]; // 向前回退}if (s[i] == s[j + 1]) { // 找到相同的前后缀j++;}next[i] = j; // 将j（前缀的长度）赋给next[i]}}int strStr(string haystack, string needle) {if (needle.size() == 0) {return 0;}vector<int> next(needle.size());getNext(&next[0], needle);int j = -1; // // 因为next数组里记录的起始位置为-1for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配j = next[j]; // j 寻找之前匹配的位置}if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动j++; // i的增加在for循环里}if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串treturn (i - needle.size() + 1);}}return -1;}
};

• 前缀表（不减一）C++实现

 class Solution {
public:void getNext(int* next, const string& s) {int j = 0;next[0] = 0;for(int i = 1; i < s.size(); i++) {while (j > 0 && s[i] != s[j]) {j = next[j - 1];}if (s[i] == s[j]) {j++;}next[i] = j;}}int strStr(string haystack, string needle) {if (needle.size() == 0) {return 0;}vector<int> next(needle.size());getNext(&next[0], needle);int j = 0;for (int i = 0; i < haystack.size(); i++) {while(j > 0 && haystack[i] != needle[j]) {j = next[j - 1];}if (haystack[i] == needle[j]) {j++;}if (j == needle.size() ) {return (i - needle.size() + 1);}}return -1;}
};