Java, one path, 18 ms, beats 87% seems to be readable


  • 0
    P
    public class Solution {
        public List<Integer> findAnagrams(String s, String p) 
        {
            int couterNums = 256;
            List<Integer> res = new ArrayList<Integer>(s.length());
            int charCounters[] = new int[couterNums];
            int pCharCounters[] = new int[couterNums];
            // initialization. count every char appearance in the p and save in pCharCounters
            for(int j = 0; j < p.length(); ++j)
            {
                ++pCharCounters[(int)p.charAt(j)];
            }
            java.util.Arrays.fill(charCounters, 0, couterNums - 1, 0);
            // count char appearance in s and save in charCounters
            int starti = 0, counter = 0, plen = p.length();
            for(int i = 0; i < s.length(); ++i)
            {
                int charIndx = (int)s.charAt(i);
    
                if(pCharCounters[charIndx] == 0) // s char is not in p - start over from the next char/i
                {
                    counter = 0; starti = i + 1;
                    cleanCounters(charCounters, p);
                }
                else // s char is in the p, increment char counters
                {
                    ++charCounters[charIndx];
                    if(charCounters[charIndx] > pCharCounters[charIndx])
                    { //this char appears too many times, "slide window", discount first char in "window"
                        --charCounters[s.charAt(starti)];
                        ++starti;
                    }
                    else
                        ++counter;
                        
                    if(counter == plen)
                    { // we found anagram so save it and slide "window" right, decrement counter 
                        res.add(starti);
                        --charCounters[s.charAt(starti)];
                        ++starti; --counter;
                    }
                }
            }
            
            return res;
        }
        
        private void cleanCounters(int charsCounters[], String str)
        {
            int strlen = str.length();
            for(int j = 0; j < strlen; ++j)
            {
                charsCounters[(int)str.charAt(j)] = 0;
            }
        }
    }
    

Log in to reply
 

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