Jump and accelerated sliding window. AC Solution.


  • 0
    I
    public IList<int> FindAnagrams(string s, string p) {
            var l = 0; //lower pointer
            var h = 0; //high pointer
            var a = new int[26]; //sliding window character count
            var b = new int[26]; //reference character count 
            var list = new List<int>();
            
            foreach(var c in p) //initialize reference array b
                b[c-'a']++;
            
            while(h < s.Length)
            {
                if(b[s[h]-'a']==0) //If a character in s doesn't exist in p, then jump
                {
                    l = h + 1;
                    a = new int[26];
                }
                else
                {
                    a[s[h]-'a']++;
                    if(FindAnagrams(a,b)) //Test if an anagram is found
                    {
                       list.Add(l);
                       a[s[l++]-'a']--; //Move lower pointer by 1, reduce character count in sliding window by 1 
                    }
                    while(a[s[h]-'a'] > b[s[h]-'a']) //accelerate lower pointer move 
                    {
                       a[s[l++]-'a']--;
                    }
                }
                h++;
            }
            return list;
        }
        
        private bool FindAnagrams(int[] a, int[] b)
        {
            for(var i = 0; i < a.Length; i++)
               if(a[i]!=b[i]) 
                   return false;
            return true;
        }
    

Log in to reply
 

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