16ms, easy understanding JAVA solution


  • 0

    Instead of using one map in the highest votes solution, I used two map here.
    It may not as short and clean as other answers, but it's easier to understand I think.

    public List<Integer> findAnagrams(String s, String p) {
    	List<Integer> anagrams = new ArrayList<>();
    	char[] pp = p.toCharArray();
    	char[] ss = s.toCharArray();
    	int[] standard = new int[26];
    	int[] copy = new int[26];
    	int left, right, count = 0;
    
    	for (int i = 0; i < pp.length; i++) {
    		standard[pp[i] - 97]++;
    	}
    
    	for (int i = 0; i < ss.length; i++) {
    		right = ss[i] - 97;
    		copy[right]++;
    		if (standard[right] == 0 || copy[right] > standard[right]) {
    			count++;
    		}
    		if (i >= pp.length) {
    			left = ss[i - pp.length] - 97;
    			copy[left]--;
    			if (standard[left] == 0 || copy[left] >= standard[left]) {
    				count--;
    			}
    		}
                    //the count is always positive, it indicates the different from p
    		if (i >= pp.length - 1 && count == 0) {
    			anagrams.add(i - pp.length + 1);
    		}
    	}
    	return anagrams;
    }
    

Log in to reply
 

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