[LintCode] Substring Anagrams

1850 ワード

Problem
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 40,000.
The order of output does not matter.
Example
Given s = "cbaebabacd"p = "abc"
return [0, 6]
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".
Solution
public class Solution {
    public List findAnagrams(String s, String p) {
    
        List res = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) return res;
        
        //since it's all lowercase English letters
        int[] sum = new int[26];
        for (char ch: p.toCharArray()) {
            sum[ch-'a']++;
        }
        
        //build a sliding window
        int start = 0, end = 0, matched = 0;
        while (end < s.length()) {
            int index = s.charAt(end) - 'a';
            if (sum[index] > 0) {
                matched++;
            } 
            sum[index]--;
            end++;
            //once the number of matched equals to p.length(), add the start index to result
            if (matched == p.length()) {
                res.add(start);
            }
            
            //move the window forward, restore `sum`
            if (end-start == p.length()) {
                if (sum[s.charAt(start)-'a'] >= 0) {
                    matched--;
                }
                sum[s.charAt(start)-'a']++;
                start++;
            }
        }
        
        return res;
    }
}