Sliding window. Very easy to understand. O(256*n) = O(n)


  • 0
    U
    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            if(p.length()>s.length()) return new ArrayList<Integer>();
            List<Integer> list = new ArrayList<Integer>();
            int[] map = new int[256];
            for(Character c: p.toCharArray()){
                map[c]++;
            }
            
            for(int i=0; i<p.length(); i++){
                map[s.charAt(i)]--;
            }
            if(checkEmpty(map)) list.add(0);
            int len = p.length();
            
            for(int i=p.length();i<s.length();i++){
                map[s.charAt(i)]--;
                map[s.charAt(i-len)]++;
                if(checkEmpty(map)) list.add(i-len+1);
            }
            return list;
            
        }
        
        public boolean checkEmpty(int[] map){
            for(int j=0; j<map.length; j++){
                if(map[j]!=0){
                    return false;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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