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

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/find-all-anagrams-in-a-string/

中文链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

题目详述

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

  • 字母异位词指字母相同，但排列不同的字符串。
  • 不考虑答案输出的顺序。

示例 1:

1
2
3
4
5
6
7
8
9
输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

1
2
3
4
5
6
7
8
9
10
输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

题目详解

滑动窗口的典型应用，有两种典型方法：固定窗口大小和不固定窗口大小。

  • 方法一：固定窗口大小，每次移动一格，判断当前窗口是否满足条件。
  • 方法二：不固定窗口大小，优先满足条件，再判断当前窗口大小是否满足要求。

固定窗口大小写法：

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
public class LeetCode_00438 {

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) {
            return res;
        }
        int[] sc = new int[26];
        int[] pc = new int[26];
        for (int i = 0; i < p.length(); ++i) {
            ++sc[s.charAt(i) - 'a'];
            ++pc[p.charAt(i) - 'a'];
        }
        if (Arrays.equals(sc, pc)) {
            res.add(0);
        }
        for (int i = p.length(); i < s.length(); ++i) {
            --sc[s.charAt(i - p.length()) - 'a'];
            ++sc[s.charAt(i) - 'a'];
            if (Arrays.equals(sc, pc)) {
                res.add(i - p.length() + 1);
            }
        }
        return res;
    }
}

不固定窗口大小写法（size 大小为不重复字母个数）：

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
public class LeetCode_00438 {

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) {
            return res;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (char c : p.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int size = map.size();
        int l = 0, r = 0;
        while (r < s.length()) {
            char c = s.charAt(r++);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0) {
                    --size;
                }
            }
            while (size == 0) {
                if (r - l == p.length()) {
                    res.add(l);
                }
                c = s.charAt(l++);
                if (map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                    if (map.get(c) > 0) {
                        ++size;
                    }
                }
            }
        }
        return res;
    }
}

不固定窗口大小写法（size 大小为所有字母个数，写法更简单，推荐）：

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
public class LeetCode_00438 {

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) {
            return res;
        }
        int[] map = new int[26];
        for (char c : p.toCharArray()) {
            ++map[c - 'a'];
        }
        int size = p.length();
        int l = 0, r = 0;
        while (r < s.length()) {
            if (--map[s.charAt(r++) - 'a'] >= 0) {
                --size;
            }
            while (size == 0) {
                if (r - l == p.length()) {
                    res.add(l);
                }
                if (++map[s.charAt(l++) - 'a'] > 0) {
                    ++size;
                }
            }
        }
        return res;
    }
}