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

Posted on In Views:

1，问题描述

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

难度：中等

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

示例 1:

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

示例 2:

1
2
3
4
5
6
输入: 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 仅包含小写字母

2，初步思考

​ 使用滑动窗来进行处理，直接选定一个大小为p.length的滑动窗口，比较这个窗口中的字符串与目标字符串中的种类个数是否一致即可

3，代码处理

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

public class _438找到字符串中所有字母异位词 {

    // 解法：滑动窗口
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length() < p.length()) return new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        char[] sCharArray = s.toCharArray();
        char[] pCharArray = p.toCharArray();
        for (char c : pCharArray) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < p.length(); i++) {
            updateMap(map, sCharArray[i], false);
        }

        for (int i = 0; i < sCharArray.length - pCharArray.length; i++) {
            if (map.isEmpty()) {
                res.add(i);
            }
            updateMap(map, sCharArray[i], true);
            updateMap(map, sCharArray[i + p.length()], false);
        }

        if (map.isEmpty()) {
            res.add(sCharArray.length - pCharArray.length);
        }

        return res;
    }

    private void updateMap(Map<Character, Integer> map, char c, boolean isInput) {
        if (isInput) {
            if (map.containsKey(c)) {
                int counter = map.get(c) + 1;
                if (counter == 0) {
                    map.remove(c);
                } else {
                    map.put(c, counter);
                }
            } else {
                map.put(c, 1);
            }
        } else {
            if (map.containsKey(c)) {
                int counter = map.get(c) - 1;
                if (counter == 0) {
                    map.remove(c);
                } else {
                    map.put(c, counter);
                }
            } else {
                map.put(c, -1);
            }
        }
    }

    public static void main(String[] args) {
        _438找到字符串中所有字母异位词 findAnagrams = new _438找到字符串中所有字母异位词();
        System.out.println(findAnagrams.findAnagrams("cbaebabacb", "abc"));
        System.out.println(findAnagrams.findAnagrams("abab", "ab"));
    }
}