用Rust🦀写算法-字符串篇

344. 反转字符串

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

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

示例 1：

1
2
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

1
2
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

  • 1 <= s.length <= 10^5
  • s[i] 都是 ASCII 码表中的可打印字符

💡 思路：

  1. 大多数语言提供了相当多库函数，这道题第一想法肯定是使用库函数，不过使用库函数不能起到锻炼作用，我们要做的是了解背后的原理
  2. 双指针法：我们使用两个指针分别指向头和末尾，交换两元素，指针向中间位移

代码（思路一）：

1
2
3
4
5
impl Solution {
    pub fn reverse_string(s: &mut Vec<char>) {
        s.reverse()
    }
}

代码（思路二）：

1
2
3
4
5
6
7
8
9
10
11
12
13
impl Solution {
    pub fn reverse_string(s: &mut Vec<char>) {
        let (mut left, mut right) = (0, s.len() - 1);
        while left < right {
            // s.swap(left,right);
            let temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left += 1;
            right -= 1;
        }
    }
}

541. 反转字符串 II

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

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

示例 1：

1
2
输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

1
2
输入：s = "abcd", k = 2
输出："bacd"

提示：

  • 1 <= s.length <= 10^4
  • s 仅由小写英文组成
  • 1 <= k <= 10^4

💡 思路：

  1. 将String转化为char数组
  2. for循环遍历，设置步长为 2 * k
  3. 反转每次循环的前k个字符 即 i..i+k
  4. 最后一次循环中，分两种情况
    a. 剩余字符少于 k 个， 即：i + k < s.len()， 反转 i..s.len()
    b. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，即还是反转前k个字符，行为同之前循环，反转 i..i+k
  5. 可以看出，循环中判断 i + k 和 s.len() 的大小，反转 i..min（较小者）即可
  6. 最后将字符数组转化为字符串即可

代码：

1
2
3
4
5
6
7
8
9
10
11
impl Solution {
    pub fn reverse_str(s: String, k: i32) -> String {
        let mut chars: Vec<char> = s.chars().collect();
        for i in (0..s.len()).step_by(2 * k as usize) {
            let end = std::cmp::min(i + k as usize, s.len());
            chars[i..end].reverse();
        }

        chars.into_iter().collect()
    }
}

54. 替换数字

给定一个字符串s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

输入描述

输入一个字符串s,s仅包含小写字母和数字字符。

输出描述

打印一个新的字符串，其中每个数字字符都被替换为了number

输入示例

1
a1b2c3

输出示例

1
anumberbnumbercnumber

提示信息

数据范围：1 <= s.length < 10000

💡 思路：新建空字符串，循环判断字符是否为数字，是的话放入”number“，不是的话直接放入

代码：

1
2
3
4
5
6
7
8
9
10
11
fn replace_numbers(s: &str) -> String {
    let mut result = String::with_capacity(s.len() * 2); // 预分配空间
    for c in s.chars() {
        if c.is_ascii_digit() {
            result.push_str("number");
        } else {
            result.push(c);
        }
    }
    result
}

151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
2
3
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

  • 1 <= s.length <= 10^4
  • s 包含英文大小写字母、数字和空格 ' '
  • s 中 至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

💡 思路：

  1. 库函数
  2. 手动实现对应函数

代码（思路一）：

1
2
3
4
5
6
7
8
impl Solution {
    pub fn reverse_words(s: String) -> String {
        s.split_whitespace()        // 分割为单词迭代器
            .rev()                     // 反转单词顺序
            .collect::<Vec<&str>>()    // 收集为Vec<&str>
            .join(" ")                 // 用空格连接单词
    }
}

代码（思路二）：

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
impl Solution {
    pub fn reverse(s: &mut Vec<char>, mut begin: usize, mut end: usize){
        while begin < end {
            let temp = s[begin];
            s[begin] = s[end];
            s[end] = temp;
            begin += 1;
            end -= 1;
        }
    }
    pub fn reverse_words(s: String) -> String {
        let mut s = s.chars().collect::<Vec<char>>();
        Self::remove_extra_spaces(&mut s);
        let len = s.len();
        Self::reverse(&mut s, 0, len - 1);
        let mut start = 0;
        for i in 0..=len {
            if i == len || s[i].is_ascii_whitespace() {
                Self::reverse(&mut s, start, i - 1);
                start = i + 1;
            }
        }
        s.iter().collect::<String>()
    }
    pub fn remove_extra_spaces(s: &mut Vec<char>) {
        let mut slow: usize = 0;
        let len = s.len();
        // 注意这里不能用for循环，不然在里面那个while循环中对i的递增会失效
        let mut i: usize = 0;
        while i < len {
            if !s[i].is_ascii_whitespace() {
                if slow != 0 {
                    s[slow] = ' ';
                    slow += 1;
                }
                while i < len && !s[i].is_ascii_whitespace() {
                    s[slow] = s[i];
                    slow += 1;
                    i += 1;
                }
            }
            i += 1;
        }
        s.resize(slow, ' ');
    }
}

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

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

示例 1：

1
2
3
4
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

1
2
3
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

  • 1 <= haystack.length, needle.length <= 104
  • haystack 和 needle 仅由小写英文字符组成

💡 思路：

  1. 暴力破解
  2. KMP算法

代码（思路一）：

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
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let mut left = 0; // 建立在haystack上的指针

        let haystack:Vec<char> = haystack.chars().collect();
        let needle:Vec<char> = needle.chars().collect();

        while left < haystack.len() {
            let mut right = 0; // 建立在needle的指针
            if haystack[left] == needle[right] { // 判断两指针是否相同
                let mut left = left; // 临时覆盖left
                left += 1; // 两指针相同 右移
                right += 1;
                // 相同时继续右移
                while left < haystack.len() && right < needle.len() && haystack[left] == needle[right] {
                    left += 1;
                    right += 1;
                }
            }
            // 如果right右移到needle末尾，说明匹配成功，初始位置为left，注意这不是上面覆盖的left
            if right == needle.len() {
                return left as i32;
            }
            // 代码走到这说明没有匹配成功，left右移继续匹配
            left += 1;
        }

        -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
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
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let next = Self::kmp_next(&needle); // 获取KMP算法next数组

        let mut i = 0; // 定义主串指针
        let mut j = 0; // 定义字串指针
        let haystack = haystack.as_bytes();
        let needle = needle.as_bytes();
        while i < haystack.len() {
            if haystack[i] == needle[j] {
                // 两指针相等 同时右移
                i += 1;
                j += 1;

                if j == needle.len() {
                    // 如果右移到字串末尾 直接返回
                    return (i - j) as i32;
                }
            } else if j > 0 {
		            // 如果已经匹配了一段字串字符后不匹配，字串指针返回到next[j -1]]
                j = next[j - 1];
            } else {
                i += 1; // 没有匹配到，主串指针右移
            }
        }

        -1
    }

    // 建立KMP算法next数组
    fn kmp_next(s: &str) -> Vec<usize> {
        let s = s.as_bytes();

        let mut i = 1; // 当前字符，从字符串第二位字符开始计算，因为第一位的最长相等前后缀的长度必为0
        let mut p_len = 0; // 相等的前后缀长度
        let mut next = vec![0; s.len()];
        while i < s.len() {
		        // 判断当前是否相等
            if s[i] == s[p_len] {
                p_len += 1; // 长度 +1
                next[i] = p_len; // 记录当前字符所在位置相等的前后缀长度
                i += 1; // 右移
            } else if p_len > 0 {
                // 不相等时，判断相等的前后缀长度大于0，指针回退到next[p_len -1]
                p_len = next[p_len - 1];
            } else {
                // 不相等，相等的前后缀长度为0，直接右移
                i += 1;
            }
        }

        next
    }
}

459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

1
2
3
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

1
2
输入: s = "aba"
输出: false

示例 3:

1
2
3
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

  • 1 <= s.length <= 104
  • s 由小写英文字母组成

💡 思路：

  1. 暴力破解：一个for循环获取 子串的终止位置， 然后判断子串是否能重复构成字符串
  2. 利用KMP算法：
    1. 如果 s 由 t 重复 k 次构成（**s = t + t + ... + t**），那么：
      a. s 的最长相同前后缀是 **t + t + ... + t**（共 k-1 个 **t**）。
      b. **next[n-1] = (k-1) * len(t)**。
    2. 所以有 **len(t) = n - next[n-1]**。
    3. 如果 **next[n-1] = 0**，说明 s 没有相同前后缀，无法由子串重复构成。
    4. 如果 **n % pattern_len != 0**，说明 len(t) 不能整除 **n**，即无法完整重复。
    4.  如果 **`n % pattern_len != 0`**，说明 **`len(t)`** 不能整除 **`n`**，即无法完整重复。

代码（思路一）：

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
impl Solution {
    pub fn repeated_substring_pattern(s: String) -> bool {
        // 暴力破解
        let n = s.len();
        if n <= 1 {
            return false;
        }

        // 检查前n/2个字符能构成的字串
        for len in 1..=n/2 {
            // 字串长度需要能被主串长度整除
            if n % len != 0 {
                continue;
            }

            let pattern = &s[0..len];
            let mut flag = true;
            
            // 检查所有后续片段是否与第一个片段匹配
            for i in (len..n).step_by(len) {
                if pattern != &s[i..i+len] {
                    flag = false;
                    break;
                }
            }

            if flag {
                return true;
            }
        }

        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
impl Solution {
    pub fn repeated_substring_pattern(s: String) -> bool {
        let n = s.len();
        if n <= 1 {
            return false;
        }
        
        let s_bytes = s.as_bytes();
        let mut next = vec![0; n];
        
        // 构建KMP的next数组
        let mut j = 0;
        for i in 1..n {
            while j > 0 && s_bytes[i] != s_bytes[j] {
                j = next[j - 1];
            }
            if s_bytes[i] == s_bytes[j] {
                j += 1;
            }
            next[i] = j;
        }
        
        // 检查是否由重复子串构成
        let pattern_len = n - next[n - 1];
        pattern_len != n && n % pattern_len == 0
    }
}

字符串：总结篇

什么是字符串

字符串是由若干字符组成的有限序列，可以理解为一个字符数组。不过很多编程语言对字符串都有特殊规定，我们来看看C/C++中的字符串实现。

在C语言中，字符串存入数组时会在末尾加入结束符’\0’，用它来标记字符串的结束位置。

例如这段代码：

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

C++则提供了string类，它通过size接口来判断字符串长度，不需要用’\0’来标记结束。

例如这段代码：

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

那vector和string有什么区别呢？

基本操作上没有区别，但string提供了更多专门的字符串处理接口，比如重载了+运算符，而vector没有。

所以处理字符串时，我们通常会选择string类型。

要不要使用库函数

打基础时不要过度依赖库函数。

有些同学习惯直接调用substr、split、reverse等库函数，却不了解其实现原理和时间复杂度。这样在面试中被问到”分析时间复杂度”时就会束手无策。

所以建议：如果题目的核心部分能用库函数解决，反而不要用库函数。

只有当库函数只是解题过程中的小部分，而且你清楚其实现原理时，才考虑使用库函数。

双指针法

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

对于数组填充类的问题，通常可以先给数组扩容到填充后的大小，然后从后向前操作。

对于数组删除操作，在27.移除元素中也用到了双指针法。

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

有些同学会在for循环中调用erase来删除元素。这其实是O(n²)的操作，因为每次erase就需要O(n)时间。这就是不了解库函数时间复杂度的典型例子。

反转系列

字符串反转还能玩出很多花样，主要考察对代码的掌控能力。

在541.反转字符串II中，有些同学为了处理”每隔2k个字符反转前k个字符”的逻辑，写了很多代码或额外的计数器。

其实处理固定规律的字符串时，可以在for循环的表达式上做文章。

只要让i每次加2k就行了，然后判断是否需要反转区间。

因为我们要找的就是每个2k区间的起点，这样写程序会更高效。

在151.翻转字符串里的单词中，我们通过综合运用多种字符串操作来解决问题，这是一道很好的练习题。

这题通过先整体反转再局部反转的方法，实现了单词的反转。

后来我们发现字符串反转还有个绝妙的用途：通过先局部反转再整体反转实现左旋效果。

KMP

KMP的核心思想是在字符串不匹配时，利用已匹配部分的信息，避免从头重新匹配。

KMP的精髓在于前缀表。在KMP精讲中，我们详细讲解了KMP算法、前缀表的概念及其必要性。

前缀表记录了从起始位置到下标i的子串中，相同前缀后缀的最大长度。

KMP主要解决两类经典问题：

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

让我们再次明确几个关键概念：

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

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

关于前缀表是否减一，这取决于KMP的具体实现方式。在KMP精讲中，我们展示了两种不同的实现版本。

其中最关键的是理解j=next[x]这一步！

总结

字符串题目的思路往往简单，但实现起来考验代码功底。复杂的字符串题目特别能检验编程能力。

双指针法是处理字符串的常用技巧，KMP是字符串查找中最重要的算法。