代码随想录算法训练营第9天 | 28.实现 strStr()，459.重复的子字符串，字符串总结，双指针回顾

28.实现strStr()

代码随想录链接

题目

LeetCode-28

给定字符串A和B，返回B作为子串在A中出现的位置。

自己的想法

暴力法就不说了，时间复杂度\(O(m * n)\)。

优化方法是使用KMP算法来进行字符串匹配，可惜考研的时候只在王道上学了KMP怎么样手工计算next数组，代码莫得掌握。

KMP太长了，感觉自己讲不明白，详细的说明可以去看上面代码随想录的链接。这里只说明一下KMP的思想就是：字符串某个位置出现不匹配的时候，可以不用从头开始匹配，直接根据next数组跳转至已经匹配过得一部分。

题解

class Solution {
public:
    void getNext(string &s, int* next) {        // 获取字符串的next数组
        int j = 0;                              // j是前缀末尾，初始指向首位
        next[0] = j;                            // 后面一位的值为回退到字符串初始位置
        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数组中的next[i]
        }
    }

    int strStr(string haystack, string needle) {
        if (needle.size() == 0) return 0;
        int next[needle.size()];
        getNext(needle, next);                  // 根据needle获取next数组
        int j = 0;                              // j用来指向needle中的字符
        for (int i = 0; i < haystack.size(); i++) { // i用来指向haystack里的字符
            while (j > 0 && haystack[i] != needle[j]) j = next[j - 1]; // 若字符不相同，needle的指针根据next数组回退
            if (haystack[i] == needle[j]) j++;   // 相同时，needle指针往后探索
            if (j == needle.size()) {            // needle指针探索到了needle的末尾时，证明匹配完成
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

459.重复的子字符串

代码随想录链接

题目

LeetCode-459

判断一个字符串是否由一个子串多次重复构成。

自己的想法

暴力法

其实也可以用KMP算法来解决，如果一个字符串是由其子串多次重复而得到的，其next数组就会呈现出一定的规律。

假设重复n次来组成的串s的子串为sub，长为x, 那么s的长度为\(m * x\)，且s的最长相同前后缀长度必定为 \((m - 1) * x\)，通过这个条件，就可以根据next数组判断是否满足题设。

题解

class Solution {
public:
    void getNext(int *next, const string &s) {              // 和上题一样，根据给定字符串获得一个next数组
        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 next[s.size()];
        getNext(next, s);
        int len = s.size();
        if (next[len - 1] != 0 && (len % (len - next[len - 1]) == 0)) {     // 如果next数组的最后一位不指向0，且字符串长度能够整除以最长前后缀以外的部分的长度，则满足条件
            return true;
        }
        return false;
    }
};

字符串总结

字符串，其实可以看做是字符的数组。在C++中，字符串可以是

char a[5] = "asd";
\\ 也可以是
vector<char> vc;
\\ 还可以是
string s;

使用char的数组来组成一个字符串，需要自行判断'\0‘来检测字符串的结尾，string则不用，且string类型提供了更多的接口来进行字符串处理。所以在遇到字符串问题的时候，尽量还是使用string类型。

双指针法

和数组中的双指针法非常相似，无论是翻转，还是去除某些元素。

例题：

• 344.反转字符串

• 字符串：替换空格

• 151.翻转字符串里的单词

反转题目

这类题目涉及到对于字符串的翻转操作，按照要求完成一部分翻转或者是某个区间的翻转。

例题：

• 541. 反转字符串II

• 151.翻转字符串里的单词

• 剑指Offer58-II.左旋转字符串

KMP

两个字符串进行匹配，思想是匹配过程中出现不相同字符时，使用预先计算好的内容，避免从头开始重新进行匹配。

例题：

• 28.实现 strStr()

• 459.重复的子字符串

双指针回顾

双指针主要是用于将暴力法（通常情况下）的\(O(n^2)\)的时间复杂度给降低下来，使用两个指针在一个for循环下完成两个嵌套for循环的工作。

字符串

主要涉及原地翻转，去除给定字符操作。（其实在数组里也是这些）

例题：

• 344.反转字符串

• 剑指Offer 05.替换空格

• 151.翻转字符串里的单词

链表

还是反转，反转链表；以及环形结构的问题。

例题：

• 206.反转链表

• 142.环形链表II

N数之和

例题：

• 15.三数之和

• 18.四数之和