【算法学习】五、找到字符串中所有字母异位词（Rust 解法）

Algorithms
, ,

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重新排列形成的字符串（包括相同的字符串）。

示例

1
2
3
4
5
6
7
8
9
10
11
12
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

解法一：排序比较

思路分析

最直观的方法是：对于 s 中每个长度为 p.len() 的子串，将其排序后与排序后的 p 进行比较。

代码实现

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
struct Solution;

impl Solution {
    pub fn find_anagrams(s: String, p: String) -> Vec<i32> {
        let mut right_str: Vec<char> = p.chars().collect();
        right_str.sort();
        let str_length = p.len();
        let mut result: Vec<i32> = Vec::new();

        if p.len() > s.len() {
            return vec![];
        }

        for i in 0..=s.len() - str_length {
            let mut left_str: Vec<char> = s[i..i + str_length].chars().collect();
            left_str.sort();
            if left_str == right_str {
                result.push(i as i32);
            } else {
                continue;
            }
        }

        result
    }
}

fn main() {
    println!(
        "{:#?}",
        Solution::find_anagrams("cbaebabacd".to_string(), "abc".to_string())
    );
}

复杂度分析

  • 时间复杂度：O(n × m log m)，其中 n 是 s 的长度，m 是 p 的长度。对于每个子串都需要排序。
  • 空间复杂度：O(m)，用于存储排序后的字符数组。

解法二：滑动窗口 + 字符计数

思路分析

更高效的方法是使用滑动窗口和字符计数：

  1. 统计 p 中每个字符的出现次数
  2. 使用固定大小的滑动窗口遍历 s
  3. 统计窗口中每个字符的出现次数
  4. 比较两个计数数组是否相同

代码实现

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
use std::collections::HashMap;

struct Solution;

impl Solution {
    pub fn find_anagrams(s: String, p: String) -> Vec<i32> {
        let s_chars: Vec<char> = s.chars().collect();
        let p_chars: Vec<char> = p.chars().collect();
        let n = s_chars.len();
        let m = p_chars.len();
        let mut result = Vec::new();

        if m > n {
            return result;
        }

        // 统计 p 中字符的频率
        let mut p_count = [0; 26];
        for &ch in &p_chars {
            p_count[(ch as u8 - b'a') as usize] += 1;
        }

        // 滑动窗口统计 s 中字符的频率
        let mut window_count = [0; 26];
        for i in 0..n {
            // 添加新字符到窗口
            window_count[(s_chars[i] as u8 - b'a') as usize] += 1;
            
            // 如果窗口大小超过 m，移除最左边的字符
            if i >= m {
                window_count[(s_chars[i - m] as u8 - b'a') as usize] -= 1;
            }
            
            // 如果窗口大小等于 m，比较频率
            if i >= m - 1 && window_count == p_count {
                result.push((i - m + 1) as i32);
            }
        }

        result
    }
}

复杂度分析

  • 时间复杂度：O(n)，只需要遍历 s 一次
  • 空间复杂度：O(1)，使用固定大小的数组（26个字母）

算法演示

解法一：排序比较

以 s = "cbaebabacd", p = "abc" 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
p 排序后: "abc"

遍历 s 的子串：
1. s[0:3] = "cba" → 排序后 "abc" → 匹配 → result = [0]
2. s[1:4] = "bae" → 排序后 "abe" → 不匹配
3. s[2:5] = "aeb" → 排序后 "abe" → 不匹配
4. s[3:6] = "eba" → 排序后 "abe" → 不匹配
5. s[4:7] = "bab" → 排序后 "abb" → 不匹配
6. s[5:8] = "aba" → 排序后 "aab" → 不匹配
7. s[6:9] = "bac" → 排序后 "abc" → 匹配 → result = [0, 6]
8. s[7:10] = "acd" → 排序后 "acd" → 不匹配

最终结果: [0, 6]

解法二：滑动窗口 + 字符计数

以 s = "cbaebabacd", p = "abc" 为例：

  • 窗口大小永远是 m（p 的长度）。
  • 窗口里永远只统计当前这 m 个字母的出现次数，不会多也不会少。
  • window_count 就是一个长度为 26 的计数器，下标 0–25 分别对应 'a'–'z'。
初始化
1
2
p_count = [1,1,1,0,0,...,0]  // a,b,c 各出现 1 次
window_count = [0,0,0,...,0]  // 全 0

第 0 步：i = 0，字符 ‘c’

1
2
window_count[2] += 1  → [0,0,1,...]
窗口大小 = 1 < 3，还不完整，不比较

第 1 步：i = 1，字符 ‘b’

1
2
window_count[1] += 1  → [0,1,1,...]
窗口大小 = 2 < 3，不比较

第 2 步：i = 2，字符 ‘a’

1
2
3
window_count[0] += 1  → [1,1,1,...]
窗口大小 = 3 == m，第一次完整窗口
比较 window_count == p_count → 相等，把起点 0 加入结果

第 3 步：i = 3，字符 ‘e’

1
2
3
4
window_count[4] += 1  → [1,1,1,0,1,...]
i >= m → 需要把 i-m=0 位置的字符 'c' 踢出去
window_count[2] -= 1  → [1,1,0,0,1,...]
窗口现在统计的是 "bae"，与 "abc" 不匹配

第 4 步：i = 4，字符 ‘b’

1
2
3
4
window_count[1] += 1  → [1,2,0,0,1,...]
踢掉 i-m=1 位置的字符 'b'
window_count[1] -= 1  → [1,1,0,0,1,...]
窗口现在是 "aeb"，不匹配

第 5 步：i = 5，字符 ‘a’

1
2
3
4
window_count[0] += 1  → [2,1,0,0,1,...]
踢掉 i-m=2 位置的字符 'a'
window_count[0] -= 1  → [1,1,0,0,1,...]
窗口现在是 "eba"，不匹配

第 6 步：i = 6，字符 ‘b’

1
2
3
4
window_count[1] += 1  → [1,2,0,0,1,...]
踢掉 i-m=3 位置的字符 'e'
window_count[4] -= 1  → [1,2,0,0,0,...]
窗口现在是 "bab"，不匹配

第 7 步：i = 7，字符 ‘a’

1
2
3
4
window_count[0] += 1  → [2,2,0,0,0,...]
踢掉 i-m=4 位置的字符 'b'
window_count[1] -= 1  → [2,1,0,0,0,...]
窗口现在是 "aba"，不匹配

第 8 步：i = 8，字符 ‘c’

1
2
3
4
window_count[2] += 1  → [2,1,1,0,0,...]
踢掉 i-m=5 位置的字符 'a'
window_count[0] -= 1  → [1,1,1,0,0,...]
窗口现在是 "bac"，与 p_count 完全一致 → 把起点 6 加入结果

第 9 步：i = 9，字符 ‘d’

1
2
3
4
window_count[3] += 1  → [1,1,1,1,0,...]
踢掉 i-m=6 位置的字符 'b'
window_count[1] -= 1  → [1,0,1,1,0,...]
窗口现在是 "acd"，不匹配

每次循环：先把新字符加进来；如果窗口超长了，就把最早进来的那个字符踢出去；只要窗口长度正好等于 m，就立即比较一次计数器。

1
2
3
4
5
6
7
8
9
10
11
12
// 1. 把新字符纳入窗口
window_count[(s_chars[i] as u8 - b'a') as usize] += 1;

// 2. 如果窗口超长了，踢掉最左边字符
if i >= m {
    window_count[(s_chars[i - m] as u8 - b'a') as usize] -= 1;
}

// 3. 只要窗口完整，就比对一次
if i >= m - 1 && window_count == p_count {
    result.push((i - m + 1) as i32);
}