【重点】【滑动窗口】438. 找到字符串中所有字母异位词

题目
重点学习《算法小抄》上关于滑动窗口模板几道题的总结对比！

Python

Counter最优版

参考：灵茶山艾府

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        cntS = Counter()
        cntP = Counter(p)
        res = []
        left, n = 0, len(p)
        for right, x in enumerate(s):
            cntS[x] += 1
            if right - left + 1 == n:
                if cntS == cntP:
                    res.append(left)
                cntS[s[left]] -= 1
                left += 1
        
        return res

原始版

注意：ord是python中把字符转为对应ASCII码值的函数！

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = list()
        l = r = 0
        win = [0] * 256
        need = [0] * 256
        for tmp_val in list(p):
            need[ord(tmp_val)] += 1
        
        valid = 0
        s_list = list(s)
        p_list = list(p)
        while r < len(s_list):
            # 右窗口右移
            cur = s_list[r]
            r += 1
            if need[ord(cur)] > 0:
                win[ord(cur)] += 1
                if win[ord(cur)] == need[ord(cur)]:
                    valid += 1

            while r - l >= len(p): # 左窗口右移
                if valid == len(set(p_list)):
                    res.append(l)
                char_rm = s[l]
                l += 1
                if need[ord(char_rm)] > 0:
                    if win[ord(char_rm)] == need[ord(char_rm)]:
                        valid -= 1
                    win[ord(char_rm)] -= 1
        
        return res

最常见思路版

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = list()
        i = 0
        sort_p = sorted(p) # 一定提前排好序!!!
        len_p = len(p)
        while i <= len(s) - len(p):
            tmp_str = sorted(s[i: i + len_p])
            if tmp_str == sort_p:
                res.append(i)
            i += 1
        return res

Java

1.滑动窗口

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        char[] sArray = s.toCharArray();
        char[] pArray = p.toCharArray();
        int[] need = new int[256];
        Set<Character> set = new HashSet<>();
        int[] window = new int[256];
        for (char c : pArray) {
            ++need[c];
            set.add(c);
        }
        int valid = 0,left = 0, right = 0;
        while (right < sArray.length) {
            char cur = sArray[right];
            ++right;
            if (need[cur] > 0) {
                ++window[cur];
                if (need[cur] == window[cur]) {
                    ++valid;
                }
            }
            while (right - left >= pArray.length) {
                if (valid == set.size()) {
                    res.add(left);
                }
                char d = sArray[left];
                ++left;
                if (need[d] > 0) {
                    if (window[d] == need[d]) {
                        --valid;
                    }
                    --window[d];
                }
            }
        }

        return res;
    }
}

2.自己想的垃圾方法

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        char[] sArray = s.toCharArray();
        char[] pArray = p.toCharArray();
        Arrays.sort(pArray);
        String pSorted = String.valueOf(pArray);
        Set<Character> pSet = new HashSet<>();
        for (char c : pArray) {
            pSet.add(c);
        }

        for (int i = 0; i <= s.length() - p.length(); ++i) {
            if (!pSet.contains(sArray[i])) {
                continue;
            }
            
            char[] tmpArray = new char[p.length()];
            for (int j = i; j - i < p.length(); ++j) {
                tmpArray[j - i] = sArray[j];
            }
            Arrays.sort(tmpArray);
            String tmp = String.valueOf(tmpArray);
            if (tmp.equals(pSorted)) {
                res.add(i);
            }
        }

        return res;
    }
}