[LeetCode] Problem 438 - Find All Anagrams in a String

Posted on | In ,

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example

No.1

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.

No.2

Input:
s: “abab” p: “ab”

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    int[] count = new int[26];

    if (s.length() < p.length())
        return result;

    for (char ch : p.toCharArray())
        count[ch - 'a']++;

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

        if (i >= p.length())
            count[s.charAt(i - p.length()) - 'a']++;

        if (match(count))
            result.add(i - p.length() + 1);
    }

    return result;
}

private boolean match(int[] count) {
    for (int c : count) {
        if (c != 0)
            return false;
    }

    return true;
}