Leetcode 438. Find All Anagrams in a String

题目

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 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".

Example 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".

思路

我们先从最简单的情况开始思考：p中没有重复的字母。比如s = cbadeacb, p = abc. 这时我们可以运用HashSet保存p中的所有字母，用双指针遍历s中所有的substring。这里双指针为：left指向substring的开始，从s的开始一直走到s.length - p.length的位置，以检查s中的所有substring。对于每个left，right从left位置一直跑到left + p.length，以检查s中长度和p相同的substring是否是p的anagram。我们可以设一个count变量，以记录在substring中字母是p中字母的次数，如果count等于p.length，则说明我们找到了anagram.

当p中有重复字母时，情况变得稍微复杂一些了。我们不仅需要记录p中每个字母出现的次数，还得检查在s的substring里面，是不是所有p里字母都出现了与p里相同的次数。前者可以通过HashMap来实现，以记录{char: frequency}。可是后者则较为麻烦。如果我们在检查某个substring的过程中对HashMap进行了修改，那么检查其他substring的时候结果就不会准确。这时我们需要运用sliding window的思想，在每次检查完一个substring后，并移动左指针的时，我们应该通过左指针来重置HashMap，以使HashMap正确表示p中字母及其频率。同时，因为right遇见合格字母时才改变count，left同样也只应该在遇见合格字母时重置count。

解答

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<Integer>();
        if (s == null || s.length() == 0 || p == null || p.length() == 0) return list;

        int[] map = new int[256]; // char map {char: freq}
        for (char ch : p.toCharArray()) {
            map[ch]++;
        }

        int count = p.length(); 
        int left = 0; int right = 0;
        while (right < s.length() ) {

            // find a matching char
            if (map[s.charAt(right)] > 0) count--; 
            map[s.charAt(right)]--;
            right++;

            // find an anagram
            if (count == 0) list.add(left); 

            // reset count and map using left pointer 
            if (right - left == p.length()) {
                if (map[s.charAt(left)] >= 0) count++;
                map[s.charAt(left)]++;
                left++;
            }
        }
        return list;
    }
}

Complexity Analysis

• Time Complexity: O(n). 我们的左右指针会以sliding window的方式各自遍历整个数组。

• Space Complexity: O(1). 我们虽然使用了map来储存字母出现次数，但是由于字母个数的有限的（255），这个map只会占用constant space。

拓展

除了FindAnagram以外，我们还有很多类似的substring可以用类似的sliding windows的方法来解决。以下为这一大类问题的算法模板：

int findSubstring(string s){
        vector<int> map(128,0);
        int counter; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one  head
        int d; //the length of substring

        for() { /* initialize the hash map here */ }

        while(end<s.size()){

            if(map[s[end++]]-- ?){  /* modify counter here */ }

            while(/* counter condition */){ 

                 /* update d here if finding minimum*/

                //increase begin to make it invalid/valid again

                if(map[s[begin++]]++ ?){ /*modify counter here*/ }
            }  

            /* update d here if finding maximum*/
        }
        return d;
  }

总结

Substring类问题核心在于如何找到substring、如何在过程中更新两头的指针、以及如何判断substring是否为valid。抓住以上几个要点后，我们则可以应用上面的通用算法思路，去解决细节不同但本质一样的各种substring类题目。

Reference

• zjh08177
• chaoyanghe's sliding window template: Very Helpful.
• [NathanNi's solution](https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92015/ShortestConcise-JAVA-O(n)-Sliding-Window-Solution)