Problem

Given a stringsand anon-emptystringp, find all the start indices ofp's anagrams ins.

Strings consists of lowercase English letters only and the length of both stringssandpwill not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:

s: "cbaebabacd" p: "abc"


Output:

[0, 6]


Explanation:

The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:

s: "abab" p: "ab"


Output:

[0, 1, 2]


Explanation:

The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

思路

• 问题
  • what is anagrams?
  • it is a substring or subsequence?
    • substring
• 暴力解法
  • TLE
  • 从起始位置开始, 形成一个窗口, 然后用hashmap检测窗口内的是否符合要求, 然后移动这个窗口

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s == null || p == null || p.length() > s.length()) {
            return res;
        }
        HashMap<Character, Integer> originalMap = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            char c = p.charAt(i);
            originalMap.put(c, originalMap.getOrDefault(c, 0) + 1);
        }
        for (int i = 0; i <= s.length() - p.length(); i++) {
            HashMap<Character, Integer> map = new HashMap<>(originalMap);
            for (int j = 0; j < p.length(); j++) {
                char c = s.charAt(i + j);
                if (!map.containsKey(c)) {
                    break;
                }
                int count = map.get(c);
                if (count == 1) map.remove(c);
                else map.put(c, map.get(c) - 1);
                if (map.isEmpty()) {
                    res.add(i);
                    break;
                }
            }

        }
        return res;
    }

• 模板套路
  • 这里count == 0, 不代表符合要求了, 有可能是"abababc", 这种情况count == 0, 但是长度不符合, 所以start需要继续增加

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s == null || p == null || p.length() > s.length()) {
            return res;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            char c = p.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        // int count = map.size();
        int count = p.length();
        int start = 0;
        int end = 0;
        while (end < s.length()) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)) {
                map.put(ch, map.get(ch) - 1);
                // if (map.get(ch) == 0) count--;
                if (map.get(ch) >= 0) count--;
            }
            end++;
            // 这里count == 0, 不代表符合要求了, 有可能是"abababc", 这种情况count == 0, 但是长度不符合, 所以start需要继续增加
            while (count == 0) {
                char startCh = s.charAt(start);
                if (map.containsKey(startCh)) {
                    map.put(startCh, map.get(startCh) + 1);
                    if (map.get(startCh) > 0) count++;
                }
                if (end - start == p.length()) {
                    res.add(start);
                }
                start++;
            }
        }
        return res;
    }