leetcode 438

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

解题 ：比较容易想到的解法就是window slide， 用一个和p 大小一样的queue来维护一个window，来比较两个字符串是不是anagrams。但是那样是时间复杂度是o(n*m)，我们可以用两个pointer来达到o（n）解法，首先我们要有个map，这里用了数组sum，如果需要考虑其他字符就设置为256长度。然后把字符串p里面的字符出现频率放进sum里面。 用一个start指针，一个end指针分别指向window两端，end需要处理看新加入的字符是否在map里面，如果在我们就把matched count加1，然后把map里面对应count减1. start需要每次调整match count和map里面的count。

class Solution {
        public List<Integer> findAnagrams(String s, String p) {
        // Write your code here
        List<Integer> ans = new ArrayList<Integer>();
        int[] sum = new int[30];

            int pLen = p.length();
            int sLen = s.length();
            for (char c : p.toCharArray()) {
                sum[c - 'a']++;
            }

            int start = 0, end = 0, matched = 0;
            while (end < sLen) {
                //first part deal end pointer, if there is match in end, matched++ and move the count in sum
                if (sum[s.charAt(end) - 'a'] >= 1) {
                    matched++;
                }
                sum[s.charAt(end) - 'a']--;
                end++;

                //when we find a match
                if (matched == pLen) {
                    ans.add(start);
                }

                //deal start index, move the window
                if (end - start == pLen) {
                    if (sum[s.charAt(start) - 'a'] >= 0) {
                        matched --;
                    }
                    //put the count back
                    sum[s.charAt(start) - 'a']++;
                    start++;
                }

            }
        return ans;
    }
}