Leetcode刷题方法总结—字符串全解

题型一：翻转字符串

举例Leetcode题目 反转字符串：题目地址

解题思路：使用反向双指针进行前后替换

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

---

题型二：范围翻转字符串

举例Leetcode题目 反转字符串II：题目地址

思路：这道题目其实也是模拟，实现题目中规定的反转规则就可以了

处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符

其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间

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;//满足if条件就不执行循环里的其他语句
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
            reverse(s.begin() + i, s.begin() + s.size());
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

题型三：替换字符串

举例Leetcode题目 替换空格：题目地址

思路：同向双指针直接遍历替换就行了

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

---

题型四：翻转单词字符串

举例Leetcode题目 颠倒字符串中的单词：题目地址

思路一：暴力求解，用split库函数分割单词，然后定义一个新的string字符串，最后再把单词倒序相加

思路二：移除多余空格，将整个字符反转，将每个单词反转

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

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

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++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
                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; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
        for (int i = 0; i <= s.size(); ++i) 
        {
            if (i == s.size() || s[i] == ' ') 
            { 
                //到达空格或者串尾，说明一个单词结束。进行翻转。
                reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        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
43
44
45
46
47
48

---

题型五：指定翻转字符串

举例Leetcode题目 左旋转字符串：题目地址

思路：双指针或reserve替换

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;
    }
};
1
2
3
4
5
6
7
8
9
10

---

题型六：模拟实现字符串

举例Leetcode题目 实现strStr()：题目地址

思路一：暴力匹配—我们可以让字符串 needle 与字符串 haystack 的所有长度为 m 的子串均匹配一次。为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 -1

思路二：KMP法- - -下一小节解释

class Solution {
public:
    int strStr(string haystack, string needle) 
    {
        int n = haystack.size(), m = needle.size();
        for (int i = 0; i + m <= n; i++) 
        {
            bool flag = true;
            for (int j = 0; j < m; j++) 
            {
                if (haystack[i + j] != needle[j]) 
                {
                    flag = false;
                    break;
                }
            }
            if (flag) 
            {
                return i;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

题型七：匹配字符串

举例Leetcode题目 重复的子字符串：题目地址

思路一：暴力的解法，让文本串与模式串一一匹配，就是一个for循环获取子串的终止位置， 然后判断子串是否能重复构成字符串，又嵌套一个for循环，所以是O(M*N)的时间复杂度

思路二：移动匹配–时间复杂度O(M+N)

思路三：KMP法—建议有一定基础或者自行了解下

KMP法的使用场景：在一个串中查找是否出现过另一个串，这是KMP的看家本领

KMP算法中next数组为什么遇到字符不匹配的时候可以找到上一个匹配过的位置继续匹配，靠的是有计算好的前缀表。 前缀表里，统计了各个位置为终点字符串的最长相同前后缀的长度

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

例如：aabaaf—前缀：a、aa、aab、aaba、aabaa—后缀：f、af、aaf、baaf、abaaf

前缀表的获得：—注：最长相等前后缀长度是首尾相等元素的个数

有了前缀表，我们可以知道模式串aabaaf是010120，当我们匹配到f的时候发现与文本串aabaabaaf不匹配了，则跳转到相等前缀的后一个元素开始匹配—即跳转到了b位置开始匹配

在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串，这里那字符串s：abababab 来举例，ab就是最小重复单位，如图所示：

如何找到最小重复子串：

• 步骤一：因为这是相等的前缀和后缀，t[0] 与 k[0]相同， t[1] 与 k[1]相同，所以 s[0] 一定和 s[2]相同，s[1] 一定和 s[3]相同，即：s[0]s[1]与s[2]s[3]相同
• 步骤二： 因为在同一个字符串位置，所以 t[2] 与 k[0]相同，t[3] 与 k[1]相同
• 步骤三： 因为这是相等的前缀和后缀，t[2] 与 k[2]相同 ，t[3]与k[3] 相同，所以，s[2]一定和s[4]相同，s[3]一定和s[5]相同，即：s[2]s[3] 与 s[4]s[5]相同
• 步骤四：循环往复

所以字符串s，s[0]s[1]与s[2]s[3]相同， s[2]s[3] 与 s[4]s[5]相同，s[4]s[5] 与 s[6]s[7] 相同，正是因为最长相等前后缀的规则，当一个字符串由重复子串组成的，最长相等前后缀不包含的子串就是最小重复子串

next数组的理解：

假设字符串s使用多个重复子串构成（这个子串是最小重复单位），重复出现的子字符串长度是x，所以s是由n * x组成，因为字符串s的最长相同前后缀的的长度一定是不包含s本身，所以 最长相同前后缀长度必然是m * x，而且 n - m = 1，所以如果 nx % (n - m)x = 0，就可以判定有重复出现的子字符串。

next 数组记录的就是最长相同前后缀 ，如果 next[len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度），最长相等前后缀的长度为：next[len - 1] + 1(这里的next数组是以统一减一的方式计算的，因此需要+1）

数组长度为：len，如果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:
    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; // r
        return false;
    }
};

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

class Solution {
public:
    void getNext (int* next, const string& s)
    {
        //前缀表不-1
        next[0] = 0;
        int j = 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) 
        {
            return true;
        }
        return false;
    }
};
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84