精进Leetcode每日一题-1128

这是我参与11月更文挑战的第26天，活动详情查看：2021最后一次更文挑战

目标：拼搏30天，拿到11月的Leetcode 月度勋章。今天是第 28 天。

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

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

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

分析：

今天这道题比较简单，我们可以采用滑动窗口来求解。

我们先统计出字符串 p 中每个字符的词频数，再把 p 的长度作为滑动窗口的宽度，把这个窗口在字符串 s 中移动，统计窗口中的词频数，如果在移动的过程中，窗口中的词频数与 p 的词频数相等，那么，这个窗口就是 p 的一个异位词。

举个例子，假设s = "cbaebabacd", p = "abc"，运算的过程如下：

1. p的词频:{a:1,b:1,c:1}
2. 滑动窗口开始后，窗口内词频:{a:1,b:1,c:1}，与p的词频一样，记录位置0为一个异位词；
3. 窗口右移一位，词频:{a:1,b:1,e:1}，与p的词频不一样，继续右移；
4. ...
5. 窗口右移一位，窗口内词频:{a:1,b:1,c:1}，与p的词频一样，记录位置0为一个异位词；
6. 窗口右移一位，词频:{a:1,b:1,e:1}，与p的词频不一样，已经到达头部，结束。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int m = s.length();
        int n = p.length();
        if (m < n) {
            // 如果s没p长，直接返回空列表
            return ans;
        }
        int[] sCnt = new int[26];
        int[] pCnt = new int[26];
        for (int i = 0; i < n; i++) {
            sCnt[s.charAt(i) - 'a']++;
            pCnt[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCnt, pCnt)) {
            // 初始窗口就相等
            ans.add(0);
        }
        for (int i = 0; i < m - n; i++) {
            // 窗口右移
            sCnt[s.charAt(i) - 'a']--;
            sCnt[s.charAt(i + n) - 'a']++;
            if (Arrays.equals(sCnt, pCnt)) {
                ans.add(i + 1);
            }
        }
        return ans;
    }
}
复制代码

• 时间复杂度：O(N)，
• 空间复杂度：O(N)。

提交排名