1. 反转字符串

344. 反转字符串 - 力扣（LeetCode）

双指针法：

// 我的代码
class Solution {
public:
// 时间复杂度O(n)
// 空间复杂度O(1)
    void reverseString(vector<char>& s) {
        int left = 0;                   // 左指针
        int right = s.size() - 1;       // 右指针
        int exchange = s.size() / 2;    // 需要交换的次数
        for(int i = 0; i < exchange; i++){
            int temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;     // 左指针向右移动
            right--;    // 右指针向左移动
        }
    }
};
// 这道题可以直接调用C++的库函数 reverse()直接求解，但是没有意义
// reverse(s.begin(), s.end());

代码随想录的代码：

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
        }
    }
};

其实差不多的。

2. 字符串反转 II

541. 反转字符串 II - 力扣（LeetCode）

思路：
这道题我一上来啊，就胡乱分析一通，然后为了处理逻辑：每隔2k个字符的前k个字符，写了一堆逻辑代码来统计2k，再统计前k个字符。这样或许能够将题目做出来，但是十分繁琐，显得很捞。

其实在遍历字符串的过程中，只要让 i = i + 2 k，然后判断反转的区间是前k个还是剩下的整个区间。
因为题目要找的也就是每 2 k 区间的起点，这样写，代码高效很多。（这也是我一开始疑惑的地方，为什么题目没有说明如果剩余的个数大于 2k 的时候应该进行的操作，后面看了题解发现如果大于 2k，就循环操作）

当需要固定规律一段一段去处理字符串的时候，要想想能否在for循环上做文章！！

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size(); i += 2 * k){
            // 1.每隔2k个字符的前k个进行反转
            // 2.剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if(i + k < s.size()){
                reverse(s.begin() + i, s.begin() + i + k);
                continue;
            }
            // 3.剩余字符少于 k 个，则将剩余字符全部反转
            reverse(s.begin() + i, s.begin() + s.size());
        }
        return s;
    }
};

3. 替换空格

剑指 Offer 05. 替换空格 - 力扣（LeetCode）

思路：
如果想把这道题做到极致，就不要使用额外的辅助空间了。
首先扩充数组到每个空格替换成 “%20” 之后的大小。
然后从后向前替换空格，也就是双指针法，过程如下：
i指向新长度的末尾，j指向旧长度的末尾。

其实很多数组填充类的问题，都可以预先给数组扩容到填充后的大小，然后再从后向前进行操作。

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0; // 统计空格的个数
        int sOldSize = s.size();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        // 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
        s.resize(s.size() + count * 2);
        int sNewSize = s.size();
        // 从后先前将空格替换为"%20"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
            if (s[j] != ' ') {
                s[i] = s[j];
            } else {
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i -= 2;
            }
        }
        return s;
    }
};

4. 翻转字符串里的单词

151. 翻转字符串里的单词 - 力扣（LeetCode）

思路：见代码随想录：代码随想录 - 双指针法 - 4. 翻转字符串里的单词

class Solution{
public:
    // 先将整组字符串倒过来
    void reverse(string& s, int start, int end){
        for(int i = start, j = end; i < j; i++, j--){
            swap(s[i], s[j]);
        }
    }
    // 移除冗余的空格,使用双指针(快慢指针),时间复杂度O(n)
    void removeExtraSpaces(string& s){
        int slow = 0, fast = 0;     // 定义快慢指针
        // 去掉字符串前面的空格
        while(s.size() > 0 && fast < s.size() && s[fast] == ' '){
            fast++;
        }
        // 去掉单词之间的多余的空格
        for(; fast < s.size(); fast++){
            if(fast - 1 > 0 && s[fast] == s[fast - 1] && s[fast] == ' '){
                continue;
            }
            s[slow++] = s[fast];
        }
        // 如果字符串后面有空格去掉字符串后面的空格
        if(slow - 1 > 0 && s[slow - 1] == ' '){
            s.resize(slow - 1);       // 重新调整字符串大小
        }
        else{
            s.resize(slow);
        }
    }
    // 再把倒序的字符串中的单词反转回来
    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverse(s, 0, s.size() - 1);
        for(int i = 0; i < s.size(); i++) {
            int j = i;
            // 查找单词间的空格，翻转单词
            while(j < s.size() && s[j] != ' ') j++;
            reverse(s, i, j - 1);
            i = j;
        }
        return s;
    }
};

5. 左旋转字符串

剑指Offer 58 - II. 左旋转字符串 - 力扣（LeetCode）

思路：
要善用 C++ 的 STL 库。reverse() 函数就是 C++标准库的函数，reverse 没有返回值
reverse(s.begin(), s.end())，区间是：[ s.begin(), s.end() )，左开右闭。

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.end());            // 整体反转
        reverse(s.begin(), s.end() - n);        // 局部反转
        reverse(s.end() - n, s.end());
        return s;
    }
};

6. KMP算法

28. 实现 strStr() - 力扣（LeetCode）

学习KMP算法首先需要明确几个概念：

1. KMP算法是用来干什么的？
2. 什么是前缀表
3. 为什么一定要用前缀表
4. 如何计算前缀表
5. 前缀表与next数组
6. 使用next数组来匹配
7. 时间复杂度分析
8. 构造next数组
9. 使用next数组来做匹配
10. 前缀表统一减一C++代码实现
11. 前缀表不减一C++代码实现
12. 总结

KMP是用来干什么的

KMP主要应用在字符串匹配上。

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配。

所以如何记录已经匹配的文本内容，是KMP的终点，也是next数组肩负的责任。

什么是前缀表

前缀表：记录下标i之前（包括下标i）的字符串中，有多大长度的相同前缀后缀。
前缀：前缀是指不包括最后一个字符的所有以第一个字符开头的连续子串。
后缀：后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

举个例子：字符串 a a b a a f
前缀:   a                    后缀:        a b a a f
        a a                            b a a f
        a a b                        a a f
        a a b a                        a f
        a a b a a                    f

正确理解什么是前缀，什么是后缀很重要！

那么网上清一色都说 “KMP 最长公共前后缀” 又是什么回事呢？
我查了一遍算法导论和算法4里面的KMP的章节，都没有提到 “最长公共前后缀” 这个词，也不知道从哪里来的，我理解是用 “最长相等前后缀” 更准确一些。

因为前缀表要求的就是相同前后缀的长度。

而最长公共前后缀里面的公共，更像是在说前缀和后缀公共的长度。这其实并不是前缀表所需要的。

写过KMP的同学一定都写过next数组，那么这个next数组究竟是个啥？
next数组就是一个前缀表（prefix table）

前缀表有什么作用？
前缀表是用来回退的，它记录了模式串与主串（文本串）不匹配的时候，模式串应该从哪里开始重新匹配。

举个例子：

当出现不匹配情况的时候，指向字符 ‘f’ 的指针 j 会回退到上一个位置（至于这个位置具体是如何获取的，后面我会讲到，这里先有这个回退的概念就可以了）。

此时就要问了，前缀表是如何记录的呢？

首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，这也意味着在某个字符失配，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

正是因为前缀表有这样的特性，我们才选择使用前缀表，而不用哈希表或者二叉树这样的数据结构。

如何计算前缀表

前缀表的正确计算是理解KMP算法的关键所在。
举个例子：a b c a b c a b f ，求这串字符串的前缀表

如图：

长度为前1个字符的子串a，最长相同前后缀的长度为0。（注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。）

长度为前2个字符的子串aa，最长相同前后缀的长度为1。

长度为前3个字符的子串aab，最长相同前后缀的长度为0。
以此类推： 长度为前4个字符的子串aaba，最长相同前后缀的长度为1。 长度为前5个字符的子串aabaa，最长相同前后缀的长度为2。 长度为前6个字符的子串aabaaf，最长相同前后缀的长度为0。
那么把求得的最长相等前后缀的长度就是对应前缀表的元素，如图：
可以看出模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。
具体的代码实现如下：

void getNext(int* next, const string& s){
    int j = 0;                            // j指向相同前后缀中前缀的末尾
    next[0] = 0;                        // next[0]初始化为0
    for(int i = 1; i < s.size(); i++){    // i指向字符串的后缀
        while(j > 0 && s[i] != s[j]){    // 前后缀不相同
            j = next[j - 1];            // 往前回退
        }
        if(s[i] == s[j]){                // 找到相同的前后缀
            j++;                        // 向后移进
        }
        next[i] = j;                    // 更新next数组
    }
}

再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示：

找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。
为什么要前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀。
所以要看前一位的 前缀表的数值。
前一个字符的前缀表的数值是2， 所以把下标移动到下标2的位置继续比配。 可以再反复看一下上面的动画。
最后就在文本串中找到了和模式串匹配的子串了。

前缀表和next数组

很多KMP算法的时间都是使用next数组来做回退操作，那么next数组与前缀表有什么关系呢？

next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。
为什么这么做呢，其实也是很多文章视频没有解释清楚的地方。

其实这并不涉及到KMP的原理，而是具体实现，next数组既可以是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。

后面我会提供两种不同的实现代码，大家就明白了。

以下我们以前缀表统一减一之后的next数组来做演示。
有了next数组，就可以根据next数组来匹配文本串s，和模式串t了。

时间复杂度分析

其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是$O(n)$，之前还要单独生成next数组，时间复杂度是$O(m)$。所以整个KMP算法的时间复杂度是$O(n+m)$的。
暴力的解法显而易见是$O(n × m)$，所以KMP在字符串匹配中极大的提高的搜索的效率。
为了和力扣题目28.实现strStr保持一致，方便大家理解，以下文章统称haystack为文本串, needle为模式串。
都知道使用KMP算法，一定要构造next数组。

c++代码实现

前缀表不减一

class Solution {
public:
    // 获得next数组
    void getNext(int* next, string s){
        int j = 0;
        next[0] = 0;                        // 初始化为0
        for(int i = 1; i < s.size(); i++){  // 注意i从1开始
            while(j > 0 && s[i] != s[j]){   // 处理前缀和后缀不相等的情况
                j = next[j - 1];            // 往前回退，回退是一个连续的过程
            }
            if(s[i] == s[j]){               // 处理前缀等于后缀的情况
                j++;                        // j向后移动
            }
            next[i] = j;                    // 更新next数组
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size() == 0){                 // 如果匹配串为空，为了和C++和Java中的strstr()函数保持一致，我们返回一个0
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;                              // j一开始指向字符串第一个元素
        for(int i = 0; i < haystack.size(); i++){
            while(j > 0 && haystack[i] != needle[j]){
                j = next[j - 1];                // 找上一个位置的next值
            }
            if(haystack[i] == needle[j]){
                j++;                            // 记录前缀和后缀相等的长度
            }
            if(j == needle.size()){             // 如果j走到needle的最后一个字符的下一个字符，说明配对完毕
                return (i - needle.size() + 1); // 返回模式串needle和文本串haystack开始匹配的位置
            }
        }
        return -1;                              // haystack如果不包含needle，那么返回-1
    }
};

前缀表减一

class Solution{
public:
    void getNext(int* next, const string& s){
        int j = -1;
        next[0] = -1;
        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;                        // 更新next数组
        }
    }
    int strStr(string haystack, string needle){
        if(needle.size() == 0){
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = -1;
        for(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出现了模式t
                return i - needle.size() + 1;
            }
        }
    }
};

难点

关于 j = next[j - 1]，即向前回溯这一块我认为是 KMP 算法中最难理解的点，
即为什么可以向前回溯？
首先，要明确 j 是前缀的末尾，也代表着前缀的长度，假设 j 是不断得移进，说明 i 作为后缀的末尾已经遍历的部分与 j 作为前缀的末尾已经遍历的部分是相同的，相同的部分就是 相等前后缀，那么 j 代表的数组正好就是 “内容为从0位置开始到 i 的位置的字符串” 的最大相等前后缀长度。

所以，当遇到不匹配的时候，我们取不匹配字符的前一位字符的 next[j - 1] ，这个时候 next[j - 1] 表示在上一次匹配中的最大相等前后缀的长度，它已经匹配好了。在这里我们回退是想要看看上次匹配好的字符是否与当前失配的字符能够匹配上，如果匹配上，j 就接着移进，如果不能，就继续回退这样的操作，直到回退到不能回退（数组下标为为0），所以说回退是一个连续的过程。

7. 重复的子字符串

459. 重复的子字符串 - 力扣（LeetCode）

思路
那么寻找重复子串怎么也涉及到KMP算法了呢？
这里就要说一说next数组了，next 数组记录的就是最长相同前后缀( 字符串：KMP算法精讲(opens new window)这里介绍了什么是前缀，什么是后缀，什么又是最长相同前后缀)， 如果 next[len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。

最长相等前后缀的长度为：next[len - 1] + 1。
数组长度为：len。
如果len % (len - (next[len - 1] + 1)) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串。

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法
如图：

next[len - 1] = 7，next[len - 1] + 1 = 8，8就是此时字符串asdfasdfasdf的最长相同前后缀的长度。
(len - (next[len - 1] + 1)) 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以被 12(字符串的长度) 整除，所以说明有重复的子字符串（asdf）。

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;
        }
    }
    bool repeatedSubstringPattern(string s) {
        if(s.size() == 0){
            return false;
        }
        int len = s.size();
        int next[len];
        getNext(next, s);
        if(next[len - 1] != 0 && len % (len - next[len - 1]) == 0){
            return true;
        }
        return false;
    }
};

前缀表减一的实现方式

class Solution{
public:
    void getNext(int* next, const string& s){
        int j = -1;
        next[0] = -1;
        for(int i = 1; i < s.size(); i++){
            while(j >= 0 && s[i] != s[j + 1]){
                j = next[j];
            }
            if(s[i] == s[j + 1]){
                j++;
            }
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern (string s){
        if(s.size() == 0){
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        if(next[len - 1] != -1 && len % (len - next[len - 1] + 1) == 0){
            return true;
        }
        return false;
    }
};

这道例题也是使用KMP算法的，我没搞懂，在这里先插个眼
686. 重复叠加字符串匹配 - 力扣（LeetCode）

8. 总结

什么是字符串

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

在C语言中，把一个字符串存入一个数组时，也把结束符 ‘\0’ 存入数组，并以此作为该字符串是否结束的标志。

例如下面的代码：

char a[5] = "asd";
for (int i = 0; a[i] != '\0'; i++) {
}

在C++中，提供一个string类，string类会提供 size 接口，可以用来判断string类字符串是否结束，就不用 ‘\0’ 来判断是否结束。

例如这段代码：

string a = "asd";
for (int i = 0; i < a.size(); i++) {
}

那么vector< char > 和 string 又有什么区别呢？
其实在基本操作上没有区别，但是 string提供更多的字符串处理的相关接口，例如string 重载了+，而vector却没有。
所以想处理字符串，我们还是会定义一个string类型。

要不要使用库函数

在文章344.反转字符串(opens new window)中强调了打基础的时候，不要太迷恋于库函数。

甚至一些同学习惯于调用substr，split，reverse之类的库函数，却不知道其实现原理，也不知道其时间复杂度，这样实现出来的代码，如果在面试现场，面试官问：“分析其时间复杂度”的话，一定会一脸懵逼！

所以建议如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。
如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。

双指针法

在344.反转字符串(opens new window)，我们使用双指针法实现了反转字符串的操作，双指针法在数组，链表和字符串中很常用。

接着在字符串：替换空格(opens new window)，同样还是使用双指针法在时间复杂度$O(n)$的情况下完成替换空格。
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

那么针对数组删除操作的问题，其实在27. 移除元素(opens new window)中就已经提到了使用双指针法进行移除操作。
同样的道理在151.翻转字符串里的单词(opens new window)中我们使用$O(n)$的时间复杂度，完成了删除冗余空格。
一些同学会使用for循环里调用库函数erase来移除元素，这其实是$O(n^2)$的操作，因为erase就是$O(n)$的操作，所以这也是典型的不知道库函数的时间复杂度，上来就用的案例了。

反转系列

在反转上还可以在加一些玩法，其实考察的是对代码的掌控能力。
541. 反转字符串II(opens new window)中，一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。

其实当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。
只要让 i += (2 k)，i 每次移动 2 k 就可以了，然后判断是否需要有反转的区间。
因为要找的也就是每2 * k 区间的起点，这样写程序会高效很多。

在151.翻转字符串里的单词(opens new window)中要求翻转字符串里的单词，这道题目可以说是综合考察了字符串的多种操作。是考察字符串的好题。
这道题目通过 先整体反转再局部反转，实现了反转字符串里的单词。
后来发现反转字符串还有一个牛逼的用处，就是达到左旋的效果。
在字符串：反转个字符串还有这个用处？(opens new window)中，我们通过先局部反转再整体反转达到了左旋的效果。

KMP

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

KMP的精髓所在就是前缀表，在KMP精讲(opens new window)中提到了，什么是KMP，什么是前缀表，以及为什么要用前缀表。

前缀表：起始位置到下标i之前（包括i）的子串中，有多大长度的相同前缀后缀。
那么使用KMP可以解决两类经典问题：

1. 匹配问题：28. 实现 strStr()(opens new window)
2. 重复子串问题：459.重复的子字符串(opens new window)

再一次强调了什么是前缀，什么是后缀，什么又是最长相等前后缀。
前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串。

然后针对前缀表到底要不要减一，这其实是不同KMP实现的方式，我们在KMP精讲(opens new window)中针对之前两个问题，分别给出了两个不同版本的的KMP实现。
其中主要理解j=next[x]这一步最为关键！

需要掌握的c++标准库函数
string类中提供的函数接口：

string s;
s.size();        // 获得字符串s的大小
s.begin();
s.end();
s.erase();        // 删除数组元素
s.resize(int size);        // 调整数组的大小,参数为调整后的大小
s.reverse(s.begin(), s.end());    // 反转字符串，O(n)

erase 函数的用法，时间复杂度是 O(n)