字符串-算法总结

目录

反转字符串

替换空格

翻转字符串里的单词

左旋字符串

KMP

重复的字符字串

---

---

反转字符串

原理：

对于字符串在原地翻转问题，可以reverse。但是其本质我们可以知道是利用双指针方法。一个指向开始，一个指向结束，不断交换两个指针的值，这里交换可以用swap，或者中间变量交换。

代码如下：

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size() - 1;
        char temp;
        while (left < right)
        {
            swap(s[left],s[right]);
            left++;
            right--;
        }
    }
};

相关题目：
344. 反转字符串 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-string/541. 反转字符串 II - 力扣（LeetCode）https://leetcode.cn/problems/reverse-string-ii/

替换空格

方法：

我们主要是先计算出扩充之后的大小，以及从后遍历数组解决数据不移动问题。

统计需要扩充的大小

        int count = 0;
        int oldWidth = s.size();
        for(int i = 0; i < s.size(); i++){
            if(s[i] == ' '){
                count++;
            }
        }
        int newWidth = s.size() + count * 2;
        s.resize(newWidth);

定义两个指针，一个是旧数组末尾，一个是新数组末尾。如果不是空格，两个同时--。当遇到空格，新指针一次性移动三位，并且填充三位。

        //从后往前遍历
        for(int i = oldWidth - 1,  j = newWidth - 1; i < j; j--, i--){
            if(s[i] != ' '){
                s[j] = s[i];
            }
            else{
                s[j] = '0';
                s[j - 1] = '2';
                s[j - 2] = '%';
                j -= 2;
            }

完整代码：

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0;
        int oldWidth = s.size();
        for(int i = 0; i < s.size(); i++){
            if(s[i] == ' '){
                count++;
            }
        }
        int newWidth = s.size() + count * 2;
        s.resize(newWidth);
        //从后往前遍历
        for(int i = oldWidth - 1,  j = newWidth - 1; i < j; j--, i--){
            if(s[i] != ' '){
                s[j] = s[i];
            }
            else{
                s[j] = '0';
                s[j - 1] = '2';
                s[j - 2] = '%';
                j -= 2;
            }
        }
        return s;
        }
       
    
};

相关题目：

剑指 Offer 05. 替换空格 - 力扣（LeetCode）https://leetcode.cn/problems/ti-huan-kong-ge-lcof/

翻转字符串里的单词

方法：

思路为：去除空格，翻转字符串，对每个单词再进行翻转。

去除空格：双指针实现。首先遍历整个字符串。当遇到非‘ ’时，把快指针遍历的元素插入慢指针对应的下标。

注意：我们对于中间的单词是需要空格的，因此我们会在不是第一个起始位置的地方插入一个空格，然后开始后续的插入非空格元素。

翻转字符串：遍历字符串，利用swap进行交换

单词翻转：利用计数器。遍历整个字符串，当计数器遇到单词边界或者字符串边界时，翻转计数器对应的单词。然后更新计数器，继续找下一个单词。

整个代码如下：

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) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
        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++];
                }
            }
        }
        return s.resize(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] == ' '){
                //当i移动到边界或者碰到单词边界
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
        return s;
    }
};

相关题目：
151. 反转字符串中的单词 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-words-in-a-string/

左旋字符串

方法：

 按照上图进行翻转即可。

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.begin() + n);
        reverse(s.begin() + n , s.end());//左闭右开
        reverse(s.begin(), s.end());
        return s;
    }
};

KMP

1.当遇到不匹配时，根据前缀表找到最长相等前后缀后，只需要从前面那个位置重新开始找，因为重新找的位置满足了前面的相同。

class Solution {
public:
    void getNext(int* next,const string&s){
        int j=0;
        next[0]=0;
        for(int i=1;isize();i++){
            //把j回退到next数组下标的地方
            while(j>0&&s[i]!=s[j]){
                j=next[j-1];
            }
            //相同的话，j就前移继续判断
            if(s[i]==s[j]){
                j++;
            }
            next[i]=j;
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0){
            return 0;
        }
        int next[needle.size()];
        getNext(next,needle);
        int j=0;
        for(int i=0;isize();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;
    }
};

重复的字符字串

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        //find返回的s的首字母下标
        //find返回时，如果是不能重复的，则返回大小比原来大1
        //如果可以重复，则返回大小比原来下
        return (s + s).find(s, 1) < s.size();
 
    }
};