字符串

反转字符串

定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素

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]);
        }
    }
};

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

反转字符串II

541. 反转字符串 II

i+=(2*k)，i每次移动2*k，然后判断是否需要有反转的区间

要找的也就是每2*k区间的起点

class Solution {
public:
    void reverse(string& s,int start,int end){
        for(int i=start,j=end;i<j;i++,j--){//左闭右闭的区间[start, end]
            swap(s[i],s[j]);
        }
    }
    string reverseStr(string s, int k) {
        for(int i=0;i<s.size();i+=(2*k)){//每隔2k个字符的前k个字符反转
            if(i+k<=s.size()){//剩余字符小于2k但大于等于k个，反转前k个字符
                reverse(s,i,i+k-1);
                continue;//详见下文“引用”
            }
            reverse(s,i,s.size()-1);//剩余字符少于k个，将剩余字符全部反转
        }
        return s;
    }
};

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

C++的std::string可变，可以直接修改字符串的内容，没有创建新的字符串

Java、Python字符串不可变，必须创建一个新的字符串或字符串数组来完成反转操作

continue

此处没有continue会无条件执行第二个reverse，导致如果i+k<=s.size()，会先反转前k个字符，然后又错误地反转了从i到末尾的所有字符，覆盖了第一次反转的结果

如s=“abcdefg”，k=2

正确版本输出"bacdfeg"

错误版本输出"bacfedg"

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]);
        }
    }
    string reverseStr(string s, int k) {
        int pos=0;
        while(pos<s.size()){
            //剩余字符串大于等于k
            if(pos+k<s.size()){
                reverse(s,pos,pos+k-1);
            }else{//剩余字符串不足k
                reverse(s,pos,s.size()-1);
            }
            pos+=2*k;
        }
        return s;
    }
};

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

反转字符串里的单词

151. 反转字符串中的单词

解题思路：

移除多余空格
将整个字符串反转
将每个单词反转

回忆双指针

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]);
        }
    }
    void removeExtraSpaces(string& s){//双指针而不是erase()，使时间复杂度由O(n^2)降为O(n)
        int slow=0;
        for(int i=0;i<s.size();i++){
            if(s[i]!=' '){
                if(slow!=0){//不是第一个单词，手动给单词间加空格
                    s[slow++]=' ';
                }
                while(i<s.size()&&s[i]!=' '){
                    s[slow++]=s[i++];
                }
            }
        }
        s.resize(slow);//slow对应去除多余空格后大小
    }
    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverse(s,0,s.size()-1);
        int start=0;
        for(int i=0;i<=s.size();i++){
            if(i==s.size()||s[i]==' '){
                reverse(s,start,i-1);
                start=i+1;
            }
        }
        return s;
    }
};

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

resize()：改变字符串的长度

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

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

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++){//注意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数组里记录的起始位置为-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);
            }
        }
        return -1;
    }
};

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

重复的子字符串

459. 重复的子字符串

移动匹配

两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成

s为abcabc，那么s+s=abcabcabcabc

去掉首尾字符后变成bcabcabcabca，其中仍然包含原串abcabc

反之如果s不能由子串重复构成，比如abcd，则s+s=abcdabcd，去掉首尾后是bcdabca，找不到abcd

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t=s+s;
        t.erase(t.begin());
        t.erase(t.end()-1);
        return t.find(s)!=std::string::npos;
    }
};

时间复杂度：O(n²)
空间复杂度：O(n)

KMP算法

当最长相等前后缀不包含的子串的长度可以被字符串s的长度整除，那么不包含的子串就是s的最小重复子串

证明参考《代码随想录》

如果next[len-1]!=-1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度），最长相等前后缀的长度为：next[len-1]+1，len-(next[len-1]+1)是最长相等前后缀不包含的子串的长度

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

next[len-1]=7，next[len-1]+1=8，8就是此时字符串asdfasdfasdf的最长相同前后缀的长度

(len-(next[len-1]+1))也就是：12（字符串的长度）-8（最长公共前后缀的长度）=4，为最长相同前后缀不包含的子串长度

4可以被12（字符串的长度）整除，所以说明有重复的子字符串（asdf）

class Solution {
public:
    void getNext(int* next,const string& s){
        next[0]=-1;
        int j=-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;
    }
};

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

总结

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

使用for循环里调用库函数erase来移除元素，这其实是O(n²)的操作，因为erase就是O(n)的操作

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