438. Find All Anagrams in a String.md

LeetCode 438. Find All Anagrams in a String

超时的一个解法

思路：

class Solution {
    public List<Integer> findAnagrams(String s, String t) {
        int sLen = s.length(), tLen = t.length();
        int left, right;
        int match;
        List<Integer> res = new ArrayList<>();
        Map<Character, Integer> cnt = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0)+1);

        left = 0;
        while (left <= sLen-tLen) { // the window [left, right] traverse the whole string s
            right = left;
            match = 0;
            cnt.clear();
            while (right < left+tLen) { // the pointer right traverse the whole window and compare with string t
                char c = s.charAt(right);
                if (!need.containsKey(c))
                    break;

                cnt.put(c, cnt.getOrDefault(c, 0) + 1);
                if (need.get(c).equals(cnt.get(c))) 
                        match++;
                
                right++;
            }
            if (match == need.size()) // 只有当遍历完整个窗口，才需要判断match == tLen 
                res.add(left);
            left++;
        }
        return res;
    }
}

最后一个测试超时

分析时间复杂度： O(mn), m为字符串s的长度，n 为字符串t的长度。

解法二——滑动窗口框架

思路：

之前的滑动窗口是为了找包含字符串p的最小子串，先增长窗口找到一个满足条件的，然后缩小窗口找到当前最小的子串，最后遍历所有情况，找到全局最优。

在这里是为了找异位词，也就是包含字符串p且长度相等，但是顺序不定，同样可以用之前的思路，先增长找到包含字符串p的子串，然后缩小窗口直到找到长度等于字符串p的为止，记录下来，然后破坏match条件，继续往前找下一个，直到最后。

时间复杂度：O(n)

class Solution {
 public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int left = 0, right = 0;
        int match = 0;
        int sLen = s.length(), pLen = p.length();
        Map<Character, Integer> cnt = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        for (char c : p.toCharArray()) need.put(c, need.getOrDefault(c, 0)+1);

        int size = need.size();
        while (right < sLen) {
            char c = s.charAt(right);
            if (need.containsKey(c)) {
                cnt.put(c, cnt.getOrDefault(c, 0)+1);
                if (need.get(c).equals(cnt.get(c)))
                    match++;
            }
            right++;
            while (match == size) {
                if (right - left == pLen)
                    res.add(left);

                char c2 = s.charAt(left);
                if (need.containsKey(c2)) {
                    if (need.get(c2).equals(cnt.get(c2)))
                        match--;
                    cnt.put(c2, cnt.get(c2)-1);
                }
                left++;
            }
        }
        return res;
    }
}

还有更优解法，目前执行时间是28ms，只击败了46.38%的用户