LC.P438[找到字符串中所有字母异位词]

方法一：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int n = s.length(), m = p.length();
        int[] c1 = new int[26], c2 = new int[26];
        for (int i = 0; i < m; ++i) ++c2[p.charAt(i) - 'a'];
        for (int l = 0, r = 0; r < n; ++r) {
            ++c1[s.charAt(r) - 'a'];
            if (r - l + 1 > m) --c1[s.charAt(l++) - 'a'];
            if (check(c1, c2)) ans.add(l);
        }
        return ans;
    }

    private boolean check(int[] c1, int[] c2) {
        for (int i = 0; i < 26; ++i) {
            if (c1[i] != c2[i]) return false;
        }
        return true;
    }
}
  • 时间复杂度：$(C \times n + m)$，其中$C = 26, n = s.length(), m = p.length()$
  • 空间复杂度：$O(C)$

方法二：优化check

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        int n = s.length(), m = p.length();
        int[] cnt = new int[26];
        for (int i = 0; i < m; ++i) ++cnt[p.charAt(i) - 'a'];
        int a = 0, b = 0;
        for (int i = 0; i < 26; ++i) if (cnt[i] != 0) ++a;
        for (int l = 0, r = 0; r < n; r++) {
            if (--cnt[s.charAt(r) - 'a'] == 0) ++b;
            if (r - l + 1 > p.length() && ++cnt[s.charAt(l++) - 'a'] == 1) b--;
            if (b == a) list.add(l);
        }
        return list;
    }
}
  • 时间复杂度：$O(C + n + m)$
  • 空间复杂度：$O(C)$