Java using two hasmaps in linear time.


  • 0
    A
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            ArrayList<Integer> result = new ArrayList<Integer>();
            if (s.length() < p.length()) {
                return result;
            }
           HashMap<Character, Integer> h = new HashMap<Character, Integer>();
    		int count = 0;
    		for(int i = 0; i < p.length(); i++) {
    			if(h.containsKey(p.charAt(i))) {
    				h.put(p.charAt(i), h.get(p.charAt(i)) + 1);
    			} else {
    				h.put(p.charAt(i), 1);
    				count++;
    			}
    		}
    		
    		HashMap<Character, Integer> hx = new HashMap<Character, Integer>();
    		int countx = 0;
    		for (int i = 0; i < p.length(); i++) {
    			char c = s.charAt(i);
    			if(h.containsKey(c)) {
    				h.put(c, h.get(c) - 1);
    				if (h.get(c) == 0) {
    					count--;
    					h.remove(c);
    				}
    			} else {
    				hx.put(c,  1);
    				countx++;
    			}
    		}
    		
    		
    		if(count == 0 && countx == 0) {
    			result.add(0);
    		}
    		
    		for(int i = p.length(); i < s.length(); i++) {
    			char remove = s.charAt(i - p.length());
    			char add = s.charAt(i);
    			
    			if (h.containsKey(remove)) {
    				h.put(remove, h.get(remove) - 1);
    				if (h.get(remove) == 0) {
    					count--;
    					h.remove(remove);
    				}
    			} else if (hx.containsKey(remove)) {
    				hx.put(remove, hx.get(remove) - 1);
    				if (hx.get(remove) == 0) {
    					countx--;
    					hx.remove(remove);
    				}
    			} else {
    				hx.put(remove, 1);
    				countx++;
    			}
    			
    			if (h.containsKey(add)) {
    				h.put(add, h.get(add) - 1);
    				if (h.get(add) == 0) {
    					count--;
    					h.remove(add);
    				}
    			} else if (hx.containsKey(add)) {
    				hx.put(add, hx.get(add) - 1);
    				if (hx.get(add) == 0) {
    					countx--;
    					hx.remove(add);
    				}
    			} else {
    				hx.put(add, 1);
    				countx++;
    			}
    			
    			if(count == 0 && countx == 0) {
    				result.add(i-p.length()+1);
    			}
    			
    		}
    		
    		return result;
        }
    }
    

Log in to reply
 

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