【LeetCode热题100】--48.找到字符串中所有字母异位词

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

使用滑动窗口：
由于字符串p的异位词的长度一定与字符串p的长度相同，所以我们可以在字符串s中构造一个长度为字符串p的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串p中每种字母的数量相同，则说明当前窗口为字符串p的异位词

在算法实现中，我们可以使用数组来存储字符串p和滑动窗口中每种字母的数量

当字符串s的长度小于字符串p的长度时，字符串s中一定不存在字符串p的异位词，但是因为字符串s中无法构造长度与字符串p的长度相同的窗口，所以这种情况需要单独处理

代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Demo {
    public static List<Integer> findAnagrams(String s, String p) {

        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }


        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        List<Integer> ans = new ArrayList<Integer>();
        ans = findAnagrams(s,p);
        System.out.println(ans);

    }
}
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

在IDEA中调试进一步理解这个算法：