Sliding window, using array instead of map. 12ms


  • 0
    L
        public List<Integer> findAnagrams(String s, String p) {
            int[] countP  = new int[26];
            for(char c: p.toCharArray()){
                countP[c-'a']++;
            }
            for(int i=0; i<26; i++){
                if(countP[i] == 0) countP[i] = -1;
            }
            int l = s.length();
            int left = 0;
            int right = 0;
            char[] str = s.toCharArray();
            List<Integer> res = new LinkedList<Integer>();
            while(right < l){
                int c = str[right]-'a';
                if(countP[c] > 0){
                    countP[c] --;
                    right++;
                }else if(countP[c] == 0){
                    countP[str[left]-'a']++;
                    left++;
                }else{
                    while(left < right){
                        countP[str[left]-'a']++;
                        left++;
                    }
                    left++;
                    right++;
                }
                if(right - left == p.length()) {
                    res.add(left);
                }
            }
            return res;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.