算法刷题笔记--字符串篇

算法思路和数组类似

反转字符串

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left=0,right=s.size()-1;
        while(left<right){
            swap(s[left],s[right]);
            left++;
            right--;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11

反转字符串II

库函数的函数区间一般是左闭右开

反转字符串中的单词

输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。

将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词就正过来了。

解题思路如下：

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

举个例子，源字符串为："the sky is blue "

• 移除多余空格 : “the sky is blue”
• 字符串反转：“eulb si yks eht”
• 单词反转：“blue is sky the”

移除字符串中多余空格

public:
    string reverseWords(string s) {
        int slow=0,fast=0;
        //去掉字符串前面的空格
        while(s.size()>0&&fast<s.size()&&s[fast]==' '){
            fast++;
        }
        for(;fast<size();fast++){
            //去掉字符串中间的空格
            if(s[fast-1]==s[fast]&&s[fast]==' '){
                continue;
            }else{
                s[slow++]=s[fast];
            }
        }
        //去除末尾的空格
        if(slow-1?0&&s[slow-1]==' '){
            s.resize(slow-1);
        }else{
            s.resize(slow);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

为了减少时间复杂度不采用这种方法

removeExtraSpaces函数来移除冗余空格。
reverse反转字符串的功能

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 write=0;
            for(int read=0;read<s.size();read++){
                if(s[read]!=' '){
                    //首个单词前不需要有空格，之后的每个单词前都需要有空格，所以慢指针要先空格再++
                    if(write!=0){
                        s[write]=' ';
                        write++;
                    }
                    while(read<s.size()&&s[read]!=' '){//遍历该单词，遇到空格说明单词结束。
                        s[write]=s[read];
                        write++;
                        read++;
                    }
                }
            }
            s.resize(write);
        }
        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;

        }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

KMP算法

什么是KMP算法
KMP主要应用在字符串匹配上。
KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
什么是前缀表
next数组就是一个前缀表（prefix table）。
前缀表有什么作用呢？
前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配
最长公共前后缀

文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。

所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

如何计算前缀表(难）
j->指向前缀末尾位置
i->指向后缀末尾位置
next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）
next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度。

可以看出模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

构造next数组

构造next数组其实就是计算模式串s，前缀表的过程。 主要有如下三步：

初始化
处理前后缀不相同的情况
处理前后缀相同的情况

这个回退操作本质上是一种递推的感觉，首先知道了next[0]的回退位置，求next[1]的操作就是：如果前后缀不同则回退，相同则更新next[1]值，这时{1]再求二以此类推一部部更新完next数组值

其实这个时候是把前缀当成模式串，把后缀当成了主串，依照前缀那个字母的前一个字母的next进行跳转

之前我们比较模式串和文本串时遇到冲突是不是回退到next数组前一位代表的下标位置，现在我们也是匹配只不过匹配的时前缀(相当于模式串)和后缀(相当于文本串)

重复的子字符串

移动匹配

所以判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。

当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t=s+s;
        t.erase(t.begin());
        t.erase(t.end()-1);
        if(t.find(s)!=std::string::npos){
            return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

t.find(s) 这部分是在 t 中查找子字符串 s 的位置。如果找到了，返回子字符串 s 在 t 中的起始位置；如果没找到，返回 std::string::npos，表示没有找到。

std::string::npos 是 std::string 类型的静态成员，它代表了一个特殊的位置值，表示未找到匹配的子字符串。

所以，if (t.find(s) != std::string::npos) 这句话的意思是：如果字符串 s 在字符串 t 中找到了（即不等于 std::string::npos），则返回 true，表示 s 是由其子字符串重复构成的；否则返回 false，表示 s 不是由其子字符串重复构成的。