[Leetcode][438. 找到字符串中所有字母异位词] 滑动窗口：从HashMap，数组，再到统计字母数量之差

By Long Luo

Leetcode 438. 找到字符串中所有字母异位词 题目如下：

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

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

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

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

	示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 

提示:
1 <= s.length, p.length <= 3 * 10^4
s 和 p 仅包含小写字母

看到这道题，首先想到方法就是：

1. 统计字符串$\textit{p}$字母及其数量；
2. 使用双指针 + 滑动窗口，如果当前窗口的不同字母种类及其数量和字符串$\textit{p}$字符串一致，将当前下标增加为答案；
3. 扫描到字符串$\textit{s}$结束。

方法一：HashMap + 滑动窗口

思路与算法：

使用$\texttt{HashMap}$存储字符串$\textit{p}$的不同字母种类及其数量。

在字符串$\textit{s}$中构造一个长度为与字符串$\textit{p}$的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串$\textit{p}$中每种字母的数量相同时，则说明当前窗口为字符串$\textit{p}$的异位词。

代码如下所示：

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ans = new ArrayList<>();
    int pLen = p.length();
    int sLen = s.length();
    if (pLen > sLen) {
        return ans;
    }

    Map<Character, Integer> patMap = new HashMap<>();
    for (char ch : p.toCharArray()) {
        patMap.put(ch, patMap.getOrDefault(ch, 0) + 1);
    }

    int left = 0;
    int right = left + pLen;

    // Sliding Window
    Map<Character, Integer> winMap = new HashMap<>();
    for (int i = left; i < right; i++) {
        char ch = s.charAt(i);
        winMap.put(ch, winMap.getOrDefault(ch, 0) + 1);
    }

    if (patMap.equals(winMap)) {
        ans.add(left);
    }

    while (right < sLen) {
        char chLeft = s.charAt(left);
        winMap.put(chLeft, winMap.get(chLeft) - 1);
        if (winMap.get(chLeft) == 0) {
            winMap.remove(chLeft);
        }

        char chRight = s.charAt(right);
        winMap.put(chRight, winMap.getOrDefault(chRight, 0) + 1);

        left++;
        right++;
        if (patMap.equals(winMap)) {
            ans.add(left);
        }
    }

    return ans;  
}

复杂度分析：

• 时间复杂度：$O(m+(n-m) \times \Sigma)$，其中$n$为字符串$\textit{s}$的长度，$m$为字符串$\textit{p}$的长度，$\Sigma$为所有可能的字符数。需要$O(m)$来统计字符串$\textit{p}$中每种字母的数量；需要$O(m)$来初始化滑动窗口；需要判断$n-m+1$个滑动窗口中每种字母的数量是否与字符串$\textit{p}$中每种字母的数量相同，每次判断需要$O(\Sigma)$。因为$\textit{s}$和$\textit{p}$仅包含小写字母，所以$\Sigma=26=26$。

• 空间复杂度：$O(\Sigma)$。用于存储字符串$\textit{p}$和滑动窗口中每种字母的数量。

方法二：数组 + 滑动窗口

思路与算法：

方法一中$\texttt{HashMap}$是否相等进行比较太耗时，因为$\textit{s}$和$\textit{p}$仅包含小写字母，所以我们只需要使用数组来存储字符串$\textit{p}$和滑动窗口中每种字母的数量即可。

优化后代码如下所示：

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ans = new ArrayList<>();
    int pLen = p.length();
    int sLen = s.length();
    if (pLen > sLen) {
        return ans;
    }

    int[] pCnt = new int[26];
    // Sliding Window
    int[] wCnt = new int[26];

    for (int i = 0; i < pLen; i++) {
        pCnt[p.charAt(i) - 'a']++;
        wCnt[s.charAt(i) - 'a']++;
    }

    if (check(pCnt, wCnt)) {
        ans.add(0);
    }

    for (int i = 0; i < sLen - pLen; i++) {
        // minus left
        wCnt[s.charAt(i) - 'a']--;
        // plus right
        wCnt[s.charAt(i + pLen) - 'a']++;
        if (check(pCnt, wCnt)) {
            ans.add(i + 1);
        }
    }

    return ans;
}

public static boolean check(int[] pCnt, int[] wCnt) {
    for (int i = 0; i < 26; i++) {
        if (pCnt[i] != wCnt[i]) {
            return false;
        }
    }

    return true;
}

复杂度分析

• 时间复杂度：$O(m+(n-m) \times \Sigma)$，其中$n$为字符串$\textit{s}$的长度，$m$为字符串$\textit{p}$的长度，$\Sigma$为所有可能的字符数。需要$O(m)$来统计字符串$\textit{p}$中每种字母的数量；需要$O(m)$来初始化滑动窗口；需要判断$n-m+1$个滑动窗口中每种字母的数量是否与字符串$\textit{p}$中每种字母的数量相同，每次判断需要$O(\Sigma)$。因为$\textit{s}$和$\textit{p}$仅包含小写字母，所以$\Sigma=26=26$。

• 空间复杂度：$O(\Sigma)$。用于存储字符串$\textit{p}$和滑动窗口中每种字母的数量。

方法三：数组 + 滑动窗口

思路与算法：

每次对滑动窗口的检查都需要检查两个词频数组，复杂度为$O(26)$，实际上，只关心两个数组是否完全一致，因此可以只维护一个词频数组$\textit{cnt}$来实现。

统计滑动窗口和字符串$\textit{p}$中每种字母数量的差，使用变量$\textit{diff}$来记录当前窗口与字符串$\textit{p}$中数量不同的字母的个数，并在滑动窗口的过程中维护它，当$\textit{diff}=0$即为我们要寻找的答案。

优化后代码如下所示：

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ans = new ArrayList<>();
    int pLen = p.length();
    int sLen = s.length();
    if (pLen > sLen) {
        return ans;
    }

    int[] count = new int[26];

    for (int i = 0; i < pLen; i++) {
        count[s.charAt(i) - 'a']++;
        count[p.charAt(i) - 'a']--;
    }

    // different chars
    int diff = 0;
    for (int x : count) {
        if (x != 0) {
            diff++;
        }
    }

    if (diff == 0) {
        ans.add(0);
    }

    for (int i = 0; i < sLen - pLen; i++) {
        char leftCh = s.charAt(i);
        if (count[leftCh - 'a'] == 1) {
            diff--; // s has leftCh, p not, diff--
        } else if (count[leftCh - 'a'] == 0) {
            diff++; // both s and p has leftCh, means move right, will not equal
        }
        count[leftCh - 'a']--;

        char rightCh = s.charAt(i + pLen);
        if (count[rightCh - 'a'] == -1) {
            diff--; // p hash rightCh, s not, that means win will equal
        } else if (count[rightCh - 'a'] == 0) {
            diff++; // both s and p has rightCh, means move right, will not equal
        }
        count[rightCh - 'a']++;

        if (diff == 0) {
            ans.add(i + 1);
        }
    }

    return ans;  
}

复杂度分析

• 时间复杂度：$O(n+m+\Sigma)$，其中$n$为字符串$\textit{s}$的长度，$m$为字符串$\textit{p}$的长度，其中$\Sigma$为所有可能的字符数。需要$O(\Sigma)$来初始化$\textit{diff}$；需要$O(n-m)$来滑动窗口并判断窗口内每种字母的数量是否与字符串$\textit{p}$中每种字母的数量相同，每次判断需要$O(1)$。因为$s$和$p$仅包含小写字母，所以$\Sigma=26=26$。

• 空间复杂度：$O(\Sigma)$。用于存储滑动窗口和字符串$\textit{p}$中每种字母数量的差。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗