438 Find All Anagrams in a String

438. Find All Anagrams in a String​
1. Question
Given a strings and a non-empty stringp, find all the start indices of p's anagrams ins.
Strings consists of lowercase English letters only and the length of both stringssandpwill not be larger than 20,100.
The order of output does not matter.
Example 1:
1
Input: s: "cbaebabacd" p: "abc"
2
​
3
Output: [0, 6]
4
​
5
Explanation:
6
​
7
The substring with start index = 0 is "cba", which is an anagram of "abc".
8
The substring with start index = 6 is "bac", which is an anagram of "abc".
Copied!
Example 2:
1
Input: s: "abab" p: "ab"
2
​
3
Output: [0, 1, 2]
4
​
5
Explanation:
6
​
7
The substring with start index = 0 is "ab", which is an anagram of "ab".
8
The substring with start index = 1 is "ba", which is an anagram of "ab".
9
The substring with start index = 2 is "ab", which is an anagram of "ab".
Copied!
2. Implementation
(1) Two Pointers + Hash
1
class Solution {
2
    public List<Integer> findAnagrams(String s, String p) {
3
        List<Integer> res = new ArrayList<>();
4
​
5
        if (s == null || s.length() == 0 || p == null || p.length() == 0) {
6
            return res;
7
        }
8
​
9
        int start = 0, end = 0, count = p.length();
10
        int[] map = new int[256];
11
​
12
        for (char c : p.toCharArray()) {
13
            ++map[c];
14
        }
15
​
16
        while (end < s.length()) {
17
            if (map[s.charAt(end)] >= 1) {
18
                --count;
19
            }
20
            --map[s.charAt(end)];
21
            ++end;
22
​
23
            while (end - start - 1 == p.length()) {
24
                if (map[s.charAt(start)] >= 0) {
25
                    ++count;
26
                }
27
                ++map[s.charAt(start)];
28
                ++start;
29
            }
30
​
31
            if (count == 0) {
32
                res.add(start);
33
            }
34
        }
35
        return res;
36
    }
37
}
Copied!
3. Time & Space Complexity
Two Pointers + Hash: 时间复杂度O(n), 空间复杂度O(n)

424 Longest Repeating Character Replacement

487 Max Consecutive Ones II

Last modified 2yr ago

Copy link

Contents

438. Find All Anagrams in a String

1. Question

2. Implementation

3. Time & Space Complexity

438. Find All Anagrams in a String​

1. Question

2. Implementation

3. Time & Space Complexity

438. Find All Anagrams in a String