法算day9

[up主专用，视频内嵌代码贴在这]

找到字符串中所有字母异位词

问题描述

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

示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

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

提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

java版（滑动窗口+字符频率）

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
import java.util.ArrayList;
import java.util.List;

public class FindAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        // 创建结果列表，用于存储所有异位词的起始索引
        List<Integer> result = new ArrayList<>();
        
        // 如果s的长度小于p的长度，直接返回空结果
        if (s == null || p == null || s.length() < p.length()) {
            return result;
        }
        
        // 创建两个数组来记录字符出现的频率
        // 因为字符串只包含小写字母，所以使用长度为26的数组
        int[] pCount = new int[26];  // 记录p中每个字符的出现次数
        int[] sCount = new int[26];  // 记录当前窗口中每个字符的出现次数
        
        // 初始化p的字符频率数组
        for (int i = 0; i < p.length(); i++) {
            pCount[p.charAt(i) - 'a']++;  // 将字符映射到0-25的索引，并增加计数
        }
        
        // 初始化滑动窗口
        // 窗口大小等于p的长度，从s的开头开始
        for (int i = 0; i < p.length(); i++) {
            sCount[s.charAt(i) - 'a']++;  // 记录s中前p.length()个字符的频率
        }
        
        // 检查第一个窗口是否是p的异位词
        if (isAnagram(pCount, sCount)) {
            result.add(0);  // 如果是，添加起始索引0
        }
        
        // 滑动窗口：每次向右移动一位
        for (int i = p.length(); i < s.length(); i++) {//当前i代表右边界索引
            // 移除窗口最左边的字符
            char leftChar = s.charAt(i - p.length());//计算左边界字符位置：i - p.length()
                                                     //获取左边界字符：s.charAt(i - p.length())
            sCount[leftChar - 'a']--;//减少该字符的计数,因为该字符即将离开窗口
            
            // 添加窗口最右边的字符（新字符）
            char rightChar = s.charAt(i);//获取右边界字符
            sCount[rightChar - 'a']++;//增加该字符的计数
            
            // 检查当前窗口是否是p的异位词
            if (isAnagram(pCount, sCount)) {
                // 如果是，添加起始索引（当前索引减去p的长度加1）
                result.add(i - p.length() + 1);
            }
        }
        
        return result;
    }
    
    // 辅助方法：检查两个字符频率数组是否相同
    private boolean isAnagram(int[] pCount, int[] sCount) {
        // 遍历26个字母，比较每个字母的出现次数
        for (int i = 0; i < 26; i++) {
            if (pCount[i] != sCount[i]) {
                return false;  // 如果有任何一个字母出现次数不同，返回false
            }
        }
        return true;  // 所有字母出现次数都相同，返回true
    }
    
    // 测试代码
    public static void main(String[] args) {
        FindAnagrams solution = new FindAnagrams();
        
        // 示例1
        String s1 = "cbaebabacd";
        String p1 = "abc";
        System.out.println("输入: s = \"" + s1 + "\", p = \"" + p1 + "\"");
        System.out.println("输出: " + solution.findAnagrams(s1, p1)); // 输出: [0,6]
        
        // 示例2
        String s2 = "abab";
        String p2 = "ab";
        System.out.println("输入: s = \"" + s2 + "\", p = \"" + p2 + "\"");
        System.out.println("输出: " + solution.findAnagrams(s2, p2)); // 输出: [0,1,2]
    }
}

✅ 说明：

  1. 时间复杂度：O(n)，其中n是s的长度
  2. 空间复杂度：O(1)，因为使用了固定大小的数组

执行过程

初试状态

1
2
3
4
5
6
7
pCount: [1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
         a b c d e f g h i j k l m n o p q r s t u v w x y z
         
sCount: [1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
         a b c d e f g h i j k l m n o p q r s t u v w x y z

第一个窗口: "cba" → 匹配，添加索引0

窗口1: i=3 (索引0-2)

1
2
3
4
5
6
7
8
移除: s[0] = 'c' → sCount[2]从1变为0
添加: s[3] = 'e' → sCount[4]从0变为1

当前窗口: "bae" (索引1-3)
sCount: [1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
         a b c d e f g h i j k l m n o p q r s t u v w x y z
         
比较pCount和sCount: 不匹配

窗口2: i=4 (索引1-3)

1
2
3
4
5
6
7
8
移除: s[1] = 'b' → sCount[1]从1变为0
添加: s[4] = 'b' → sCount[1]从0变为1

当前窗口: "aeb" (索引2-4)
sCount: [1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
         a b c d e f g h i j k l m n o p q r s t u v w x y z
         
比较pCount和sCount: 不匹配

窗口3: i=5 (索引2-4)

1
2
3
4
5
6
7
8
移除: s[2] = 'a' → sCount[0]从1变为0
添加: s[5] = 'a' → sCount[0]从0变为1

当前窗口: "eba" (索引3-5)
sCount: [1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
         a b c d e f g h i j k l m n o p q r s t u v w x y z
         
比较pCount和sCount: 不匹配

窗口4: i=6 (索引3-5)

1
2
3
4
5
6
7
8
移除: s[3] = 'e' → sCount[4]从1变为0
添加: s[6] = 'b' → sCount[1]从1变为2

当前窗口: "bab" (索引4-6)
sCount: [1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
         a b c d e f g h i j k l m n o p q r s t u v w x y z
         
比较pCount和sCount: 不匹配 (b的计数不同)

窗口5: i=7 (索引4-6)

1
2
3
4
5
6
7
8
移除: s[4] = 'b' → sCount[1]从2变为1
添加: s[7] = 'a' → sCount[0]从1变为2

当前窗口: "aba" (索引5-7)
sCount: [2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
         a b c d e f g h i j k l m n o p q r s t u v w x y z
         
比较pCount和sCount: 不匹配 (a的计数不同)

窗口6: i=8 (索引5-7)

1
2
3
4
5
6
7
8
移除: s[5] = 'a' → sCount[0]从2变为1
添加: s[8] = 'c' → sCount[2]从0变为1

当前窗口: "bac" (索引6-8)
sCount: [1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
         a b c d e f g h i j k l m n o p q r s t u v w x y z
         
比较pCount和sCount: 匹配，添加索引6

窗口7: i=9 (索引6-8)

1
2
3
4
5
6
7
8
移除: s[6] = 'b' → sCount[1]从1变为0
添加: s[9] = 'd' → sCount[3]从0变为1

当前窗口: "acd" (索引7-9)
sCount: [1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
         a b c d e f g h i j k l m n o p q r s t u v w x y z
         
比较pCount和sCount: 不匹配

python版

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
from collections import defaultdict  # 导入defaultdict，它是字典的一个子类，提供默认值功能

def findAnagrams_optimized(s, p):
    """
    优化版本：使用固定大小的滑动窗口
    参数:
        s: 主字符串，我们要在其中搜索
        p: 目标字符串，我们要找它的异位词
    返回:
        result: 包含所有异位词起始索引的列表
    """
    result = []  # 初始化结果列表，用于存储找到的异位词起始索引
    
    # 边界情况检查：如果p比s长，不可能找到异位词，直接返回空列表
    if len(p) > len(s):
        return result
    
    # 使用defaultdict(int)创建两个计数器
    # defaultdict(int)会自动为不存在的键提供默认值0，避免KeyError
    p_count = defaultdict(int)  # 用于统计目标字符串p中每个字符的出现次数
    window_count = defaultdict(int)  # 用于统计当前滑动窗口中每个字符的出现次数
    
    # 初始化p的字符计数：遍历p中的每个字符，在p_count中增加对应计数
    for char in p:
        p_count[char] += 1  # 记录p中每个字符的出现次数
    
    # 初始化窗口：在s的前len(p)个字符上初始化第一个窗口
    for i in range(len(p)):
        window_count[s[i]] += 1  # 统计第一个窗口中每个字符的出现次数
    
    # 检查第一个窗口：如果第一个窗口的字符计数与p的字符计数相同，则记录起始索引0
    if window_count == p_count:
        result.append(0)  # 第一个窗口就是异位词，记录索引0
    
    # 滑动窗口：从索引len(p)开始，到s的末尾
    for i in range(len(p), len(s)):
        # 添加新字符：将当前右指针指向的字符加入窗口计数器
        window_count[s[i]] += 1
        
        # 移除旧字符：将窗口最左边的字符（即当前索引减去p长度位置的字符）从窗口计数器中移除
        window_count[s[i - len(p)]] -= 1
        
        # 如果某个字符计数减为0，则从字典中删除该键
        # 这是为了确保窗口计数器和p计数器的比较是准确的
        if window_count[s[i - len(p)]] == 0:
            del window_count[s[i - len(p)]]  # 删除计数为0的字符，避免干扰比较
        
        # 检查当前窗口：如果窗口内字符计数与p的字符计数相同，则找到异位词
        if window_count == p_count:
            # 计算当前窗口的起始索引：当前索引i减去p长度再加1
            result.append(i - len(p) + 1)
    
    return result  # 返回所有找到的异位词起始索引