字符串

Channing Hsu
  2023-07-29 13:34:42 2023-07-29 13:34:42 创建   2024-12-03 01:50:49 2024-12-03 01:50:49 更新      5.3k 字  21 分钟  

344.反转字符串

力扣题目链接

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：
输入：[“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]

示例 2：
输入：[“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]

思路

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

以字符串hello为例，过程如下：

344.反转字符串

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void reverseString(vector<char>& s) {
        // 库函数 reverse
        // reverse(s.begin(), s.end());
        // 双指针
        // 若为一个字符，直接返回
        if (s.size() == 1) return;
        // 定义快慢指针
        int slow = 0;
        int fast = s.size() - 1;
        // 首尾交换
        while ( slow < fast) {
          // swap(s[slow], s[fast]);
            char temp = s[slow];
            s[slow] = s[fast];
            s[fast] = temp;
            slow++;
            fast--;
        }
    }
};

541. 反转字符串II

力扣题目链接

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

输入: s = “abcdefg”, k = 2
输出: “bacdfeg”

思路

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

因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。

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

C++代码

使用C++库函数reverse的版本如下：

  • 时间复杂度:
  • 空间复杂度: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string reverseStr(string s, int k) {
		int n = s.size();
        for (int i = 0; i < n; i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
			int end = min(i + k, n);
            reverse(s.begin() + i, s.begin() + end);
        }
        return s;
    }
};

剑指Offer 05.替换空格

力扣题目链接

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：
输入：s = “We are happy.”
输出：“We%20are%20happy.”

思路

首先扩充数组到每个空格替换成"%20"之后的大小。

然后从后向前替换空格，也就是双指针法，过程如下：

i指向新长度的末尾，j指向旧长度的末尾。

替换空格

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

  1. 不用申请新数组。
  2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string replaceSpace(string s) {
        int count = 0, len = s.size();
        // 统计空格数量
        for (char c : s){
            if (c == ' ') count++;
        }
        // 修改s的长度
        s.resize(len + 2 * count);
        //倒序遍历修改
        for (int i = len - 1, j = s.size() - 1; i < j; i--, j--){
            if (s[i] != ' ')
                s[j] = s[i];
            else{
                s[j - 2] = '%';
                s[j - 1] = '2';
                s[j] = '0';
                j -= 2;
            }
        }
        return s;
    }
};

151.翻转字符串里的单词

力扣题目链接

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: “the sky is blue”
输出: “blue is sky the”

示例 2：
输入: "  hello world!  "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: “a good   example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路

解题思路如下：

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

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

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

C++代码

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
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 removeSpace(string& s){
        int slow = 0;
        for (int i = 0; i < s.size(); i++){
            if (s[i] != ' ') {
                // 在单词前面加空格
                if (slow != 0) s[slow++] = ' ';
                // 将单词复制到s[slow]开始的位置 
                while (i < s.size() && s[i] != ' '){
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow);
    }
    string reverseWords(string s) {
        // 移除空格
        removeSpace(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;
    }
};

58.左旋转字符串

力扣题目链接

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：
输入: s = “abcdefg”, k = 2
输出: “cdefgab”

示例 2：
输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”

限制：
1 <= k < s.length <= 10000

思路

  1. 反转区间为前n的子串
  2. 反转区间为n到末尾的子串
  3. 反转整个字符串

最后就可以达到左旋n的目的，而不用定义新的字符串，完全在本串上操作。

例如 ：示例1中 输入：字符串abcdefg，n=2

如图：

最终得到左旋2个单元的字符串：cdefgab

思路明确之后，那么代码实现就很简单了

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    // 1、使用库函数rotate
    rotate(s.begin(), s.begin() + n, s.end());
    // 2、整体翻转
    string reverseLeftWords(string s, int n) {
     		// 翻转前n个字符
      	reverse(s.begin(), s.begin() + n);
        // 翻转之后的字符
        reverse(s.begin() + n, s.end());
        // 翻转所有字符
        reverse(s.begin(), s.end());
        return s;
    }
};

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

力扣题目链接

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:
输入: haystack = “hello”, needle = “ll”
输出: 2

示例 2:
输入: haystack = “aaaaa”, needle = “bba”
输出: -1

说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

思路

本题是KMP 经典题目。

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

  1. 初始化
  2. 处理前后缀不相同的情况
  3. 处理前后缀相同的情况

1. 初始化：

定义两个指针i和j，j指向前缀末尾位置，i指向后缀末尾位置。

然后还要对next数组进行初始化赋值，如下：

1
2
int j = -1;
next[0] = j;

j 为什么要初始化为 -1呢，因为之前说过 前缀表要统一减一的操作仅仅是其中的一种实现，我们这里选择j初始化为-1，下文我还会给出j不初始化为-1的实现代码。

next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）所以初始化next[0] = j 。

2. 处理前后缀不相同的情况

因为j初始化为-1，那么i就从1开始，进行s[i] 与 s[j+1]的比较。

所以遍历模式串s的循环下标i 要从 1开始，代码如下：

1
for (int i = 1; i < s.size(); i++) {

如果 s[i] 与 s[j+1]不相同，也就是遇到 前后缀末尾不相同的情况，就要向前回退。

怎么回退呢？

next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度。

那么 s[i] 与 s[j+1] 不相同，就要找 j+1前一个元素在next数组里的值（就是next[j]）。

所以，处理前后缀不相同的情况代码如下：

1
2
3
while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
    j = next[j]; // 向前回退
}

3. 处理前后缀相同的情况

如果 s[i] 与 s[j + 1] 相同，那么就同时向后移动i 和j 说明找到了相同的前后缀，同时还要将j（前缀的长度）赋给next[i], 因为next[i]要记录相同前后缀的长度。

代码如下：

1
2
3
4
if (s[i] == s[j + 1]) { // 找到相同的前后缀
    j++;
}
next[i] = j;

最后整体构建nexÒt数组的函数代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
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]
    }
}

代码构造next数组的逻辑流程动画如下：

KMP精讲3

得到了next数组之后，就要用这个来做匹配了。

使用next数组来做匹配

在文本串s里 找是否出现过模式串t。

定义两个下标j 指向模式串起始位置，i指向文本串起始位置。

那么j初始值依然为-1，为什么呢？ 依然因为next数组里记录的起始位置为-1。

i就从0开始，遍历文本串，代码如下：

1
for (int i = 0; i < s.size(); i++) 

接下来就是 s[i] 与 t[j + 1] （因为j从-1开始的） 进行比较。

如果 s[i] 与 t[j + 1] 不相同，j就要从next数组里寻找下一个匹配的位置。

代码如下：

1
2
3
while(j >= 0 && s[i] != t[j + 1]) {
    j = next[j];
}

如果 s[i] 与 t[j + 1] 相同，那么i 和 j 同时向后移动， 代码如下：

1
2
3
if (s[i] == t[j + 1]) {
    j++; // i的增加在for循环里
}

如何判断在文本串s里出现了模式串t呢，如果j指向了模式串t的末尾，那么就说明模式串t完全匹配文本串s里的某个子串了。

本题要在文本串字符串中找出模式串出现的第一个位置 (从0开始)，所以返回当前在文本串匹配模式串的位置i 减去 模式串的长度，就是文本串字符串中出现模式串的第一个位置。

代码如下：

1
2
3
if (j == (t.size() - 1) ) {
    return (i - t.size() + 1);
}

那么使用next数组，用模式串匹配文本串的整体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
int j = -1; // 因为next数组里记录的起始位置为-1
for (int i = 0; i < s.size(); i++) { // 注意i就从0开始
    while(j >= 0 && s[i] != t[j + 1]) { // 不匹配
        j = next[j]; // j 寻找之前匹配的位置
    }
    if (s[i] == t[j + 1]) { // 匹配，j和i同时向后移动
        j++; // i的增加在for循环里
    }
    if (j == (t.size() - 1) ) { // 文本串s里出现了模式串t
        return (i - t.size() + 1);
    }
}

此时所有逻辑的代码都已经写出来了，力扣 28.实现strStr 题目的整体代码如下：

C++代码

前缀表统一减一 C++代码实现

  • 时间复杂度:
  • 空间复杂度: , 只需要保存字符串needle的前缀表
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
class Solution {
public:
    void getNext(int* next, const string& s) {
        // 1、初始化
        int j = -1;
        next[0] = j;
        for(int i = 1; i < s.size(); i++) { // 注意i从1开始
            while (j >= 0 && s[i] != s[j + 1]) { // 2、前后缀不相同了
                j = next[j]; // 向前回退
            }
            if (s[i] == s[j + 1]) { // 3、找到相同的前后缀
                j++;
            }
            next[i] = j; // 4、		将j（前缀的长度）赋给next[i]
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, 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;
    }
};

总结

我们介绍了什么是KMP，KMP可以解决什么问题，然后分析KMP算法里的next数组，知道了next数组就是前缀表，再分析为什么要是前缀表而不是什么其他表。

接着从给出的模式串中，我们一步一步的推导出了前缀表，得出前缀表无论是统一减一还是不减一得到的next数组仅仅是kmp的实现方式的不同。其中还分析了KMP算法的时间复杂度，并且和暴力方法做了对比。

然后先用前缀表统一减一得到的next数组，求得文本串s里是否出现过模式串t，并给出了具体分析代码。

又给出了直接用前缀表作为next数组，来做匹配的实现代码。可以说把KMP的每一个细微的细节都扣了出来，毫无遮掩的展示给大家了！

459.重复的子字符串

力扣题目链接

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

  • 输入: “abab”
  • 输出: True
  • 解释: 可由子字符串 “ab” 重复两次构成。

示例 2:

  • 输入: “aba”
  • 输出: False

示例 3:

  • 输入: “abcabcabcabc”
  • 输出: True
  • 解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

思路

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

如图：

459.重复的子字符串_1

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

C++代码

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
class Solution {
public:
    // 计算next数组
    void getNext(int* next, string& s){
        int j = -1;
        next[0] = j;
        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) {
        int next [s.size()];
        getNext(next, s); 
        // 整个s的最长相同前后缀
        int len = next[s.size() - 1]; 
        // 数组长度-最长相等前后缀的长度
        int subStr = s.size() - (len + 1);
        
        if (len != -1 && s.size() % subStr == 0) return true;
        return false;
    }
};

字符串：总结篇

什么是字符串

字符串是若干字符组成的有限序列，也可以理解为是一个字符数组，但是很多语言对字符串做了特殊的规定，接下来我来说一说C/C++中的字符串。

在C语言中，把一个字符串存入一个数组时，也把结束符 '\0’存入数组，并以此作为该字符串是否结束的标志。

例如这段代码：

1
2
3
char a[5] = "asd";
for (int i = 0; a[i] != '\0'; i++) {
}

在C++中，提供一个string类，string类会提供 size接口，可以用来判断string类字符串是否结束，就不用’\0’来判断是否结束。

例如这段代码:

1
2
3
string a = "asd";
for (int i = 0; i < a.size(); i++) {
}

那么vector< char > 和 string 又有什么区别呢？

其实在基本操作上没有区别，但是 string提供更多的字符串处理的相关接口，例如string 重载了+，而vector却没有。

所以想处理字符串，我们还是会定义一个string类型。

要不要使用库函数

在文章344.反转字符串中强调了打基础的时候，不要太迷恋于库函数。

甚至一些同学习惯于调用substr，split，reverse之类的库函数，却不知道其实现原理，也不知道其时间复杂度，这样实现出来的代码，如果在面试现场，面试官问：“分析其时间复杂度”的话，一定会一脸懵逼！

所以建议如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。

如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。

双指针法

在344.反转字符串 ，我们使用双指针法实现了反转字符串的操作，双指针法在数组，链表和字符串中很常用。

接着在字符串：替换空格，同样还是使用双指针法在时间复杂度O(n)的情况下完成替换空格。

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

那么针对数组删除操作的问题，其实在27. 移除元素中就已经提到了使用双指针法进行移除操作。

同样的道理在151.翻转字符串里的单词中我们使用O(n)的时间复杂度，完成了删除冗余空格。

一些同学会使用for循环里调用库函数erase来移除元素，这其实是O(n^2)的操作，因为erase就是O(n)的操作，所以这也是典型的不知道库函数的时间复杂度，上来就用的案例了。

反转系列

在反转上还可以在加一些玩法，其实考察的是对代码的掌控能力。

541. 反转字符串II中，一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。

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

只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

因为要找的也就是每2 * k 区间的起点，这样写程序会高效很多。

在151.翻转字符串里的单词中要求翻转字符串里的单词，这道题目可以说是综合考察了字符串的多种操作。是考察字符串的好题。

这道题目通过 先整体反转再局部反转，实现了反转字符串里的单词。

后来发现反转字符串还有一个牛逼的用处，就是达到左旋的效果。

在字符串：反转个字符串还有这个用处？中，我们通过先局部反转再整体反转达到了左旋的效果。

KMP

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

KMP的精髓所在就是前缀表，在KMP精讲中提到了，什么是KMP，什么是前缀表，以及为什么要用前缀表。

前缀表：起始位置到下标i之前（包括i）的子串中，有多大长度的相同前缀后缀。

那么使用KMP可以解决两类经典问题：

  1. 匹配问题：28. 实现 strStr()
  2. 重复子串问题：459.重复的子字符串

再一次强调了什么是前缀，什么是后缀，什么又是最长相等前后缀。

前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串。

然后针对前缀表到底要不要减一，这其实是不同KMP实现的方式，我们在KMP精讲中针对之前两个问题，分别给出了两个不同版本的的KMP实现。

其中主要理解j=next[x]这一步最为关键！

总结

字符串类类型的题目，往往想法比较简单，但是实现起来并不容易，复杂的字符串题目非常考验对代码的掌控能力。

双指针法是字符串处理的常客。

KMP算法是字符串查找最重要的算法，但彻底理解KMP并不容易，我们已经写了五篇KMP的文章，不断总结和完善，最终才把KMP讲清楚。

好了字符串相关的算法知识就介绍到了这里了，明天开始新的征程，大家加油！

评论
目录
字符串
  1. 344.反转字符串
    1. 思路
    2. C++代码
  2. 541. 反转字符串II
    1. 思路
    2. C++代码
  3. 剑指Offer 05.替换空格
    1. 思路
    2. C++ 代码
  4. 151.翻转字符串里的单词
    1. 思路
    2. C++代码
  5. 58.左旋转字符串
    1. 思路
    2. C++代码
  6. 28. 找出字符串中第一个匹配项的下标
    1. 思路
    2. C++代码
    3. 总结
  7. 459.重复的子字符串
    1. 思路
    2. C++代码
  8. 字符串：总结篇
    1. 什么是字符串
    2. 要不要使用库函数
    3. 双指针法
    4. 反转系列
    5. KMP
    6. 总结