问题

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

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

示例 1

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

练习

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

# your python code

思路

北海啊，要多想！

滑动窗口

需要在长字符串 s 中找到所有与短字符串 p 的字母异位词的起始索引。关键在于如何高效地判断一个子串是否是 p 的字母异位词。暴力解法是每次都重新计算子串的字符频率，但这会导致较高的时间复杂度。

可以考虑采用了滑动窗口和字符频率统计的方式进行求解。首先，统计字符串 p 中每个字符出现的频率。然后，使用一个大小为 n（p 的长度）的滑动窗口在字符串 s 上滑动。在每个窗口中，我们维护一个字符频率数组，并通过比较该数组与字符串 p 的字符频率数组来判断当前窗口内的子串是否是字母异位词。

Java

import java.util.ArrayList;  
import java.util.List;  
import java.util.Scanner;  
  
public class LC438FindAnagrams {  
    public static void main(String[] args) {  
        // Scanner scanner = new Scanner(System.in);  
        // String s = scanner.nextLine();        
        // String p = scanner.nextLine();  
        String s = "abab";  
        String p = "ab";  
  
        System.out.println(findAnagrams(s, p));  
    }  
    private static List<Integer> findAnagrams(String s, String p) {  
        List<Integer> ans = new ArrayList<>();  
        int m = s.length(), n = p.length();  
  
        int[] alphabet = new int[26];  
        for (int i = 0; i < n; i++) {  
            alphabet[(int) (p.charAt(i) - 'a')] += 1;  
        }  
        int r = 0;  
        for (int l = 0; l < m - n + 1; l++) {  
            while (r < l + n) {  
                alphabet[(int) (s.charAt(r) - 'a')] -= 1;  
                r++;  
            }  
            int num = 26;  
            for (int i = 0; i < 26; i++) {  
                if (alphabet[i] == 0) {  
                    num -= 1;  
                } else {  
                    break;  
                }            
            }            
            if (num == 0) {  
                ans.add(l);  
            }  
            alphabet[(int) (s.charAt(l) - 'a')] += 1;  
        }  
  
        return ans;  
    }
}

复杂度分析：

• 时间复杂度：$\mathcal{O}(m + (m-n)\times \lvert \Sigma \rvert)$。其中 $\Sigma$ 为可能出现的字符串集合。
• 空间复杂度：$\mathcal{O}(\lvert \Sigma \rvert)$。

优化的滑动窗口

每次窗口滑动后都要扫描一次长度 26 的数组来判断是不是全都归零，这一步是 $\mathcal{O}(26)$ 的开销，对于字符串很长时就会变重。可以用一个变量 differ 来替代每次全表扫描，只要在“入窗”和“出窗”时动态维护它，就能把每次判断从 $\mathcal{O}(26)$ 降到 $\mathcal{O}(1)$ 。

Java

import java.util.ArrayList;  
import java.util.List;  
import java.util.Scanner;  
  
public class LC438FindAnagrams {  
    public static void main(String[] args) {  
        // Scanner scanner = new Scanner(System.in);  
        // String s = scanner.nextLine();        
        // String p = scanner.nextLine();  
        String s = "abab";  
        String p = "ab";  
  
        System.out.println(findAnagrams(s, p));  
    }    
    private static List<Integer> findAnagrams(String s, String p) {  
        List<Integer> ans = new ArrayList<>();  
        int m = s.length(), n = p.length();  
  
        if (m < n) return ans;  
  
        // 初始化滑动窗口  
        int differ = 0;  
        int[] alphabet = new int[26];  
        for (int r = 0; r < n; r++) {  
            alphabet[s.charAt(r) - 'a'] += 1; // s 引起的变化 +1            
            alphabet[p.charAt(r) - 'a'] -= 1; // p 引起的变化 -1        
            }  
        for (int i = 0; i < 26; i++) {  
            if (alphabet[i] != 0) {  
                differ += 1;  
            }        
        }        
        if (differ == 0) {  
            ans.add(0);  
        }  
        // 开始滑动  
        for (int l = 0; l < m - n; l++) {  
            int out = s.charAt(l) - 'a'; // 出窗字符  
            int in = s.charAt(l + n) - 'a'; // 入窗字符  
  
            // 出窗  
            if (alphabet[out] == 1) {  
                differ -= 1;  
            }            
            if (alphabet[out] == 0) {  
                differ += 1;  
            }            
            alphabet[out] -= 1;  
  
            // 入窗  
            if (alphabet[in] == -1) {  
                differ -= 1;  
            }            
            if (alphabet[in] == 0) {  
                differ += 1;  
            }            
            alphabet[in] += 1;  
  
  
            if (differ == 0) {  
                ans.add(l+1);  
            }  
        }  
        return ans;  
    }
}

复杂度分析：

• 时间复杂度：$\mathcal{O}(m + n + \lvert \Sigma \rvert)$。其中 $\Sigma$ 为可能出现的字符串集合。
• 空间复杂度：$\mathcal{O}(\lvert \Sigma \rvert)$。