438.-find-all-anagrams-in-a-string.md

438. Find All Anagrams in a String

• Medium

• Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

  An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Analysis

This is a sliding window problem. Besides that, we need an array/dictionary to record current time of appearance of each letter. Since we only have lower case letters, we can use ascii value to give us a value in the range of [0,25].

dict.fromkeys([a,b,c,d],0) generates a dictionary that is as follows {'a':0,'b':0,'c':0,'d':0}. Here in the following code I have used fromkeys(range(26),0), which has the same effect as writing out a list [0,1,2,....,25]

Another corner case to consider is at the end of the list. When we reached the end of the list, the end pointer would be pointing outside of the target. But that is still a case we need to calculate the existence of possible anagram. So we should include that situation and check if 'end' is pointing outside before calculation.

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        length=len(p)
        lens=len(s)
        if lens<length:
            return []
        dic=dict.fromkeys(range(26),0);
        for i in range(length):
            index=ord(p[i])-ord('a')
            dic[index]+=1
        
        for i in range(length):
            index=ord(s[i])-ord('a')
            dic[index]-=1
            
        start=0
        end=length
        answer=[]
        while (end<=lens):
            ans=True
            i=0
            while (i<26 and ans):
                if (dic[i]!=0):
                    ans=False
                i+=1
            if ans:
                answer.append(start)
            inds=ord(s[start])-ord('a') 
            if end<lens:
                inde=ord(s[end])-ord('a')
                dic[inde]-=1
            dic[inds]+=1
            
            start+=1
            end+=1
        return answer

Or, since dictionaries accept characters as keys, we can use the letters themselves as keys for the job. Here "string.ascii_lowercase" creates a string containing all the lower case letters (i.e. "abcdefg...xyz"). Then we can use the function "list" to convert it to a list.

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        length=len(p)
        lens=len(s)
        alphabet=list(string.ascii_lowercase)
        if lens<length:
            return []
        dic=dict.fromkeys(alphabet,0);
        
        for i in range(length):
            dic[p[i]]+=1
        
        for i in range(length):
            dic[s[i]]-=1
            
        start=0
        end=length
        answer=[]
        while (end<=lens):
            ans=True
            i=0
            while (i<26 and ans):
                if (dic[alphabet[i]]!=0):
                    ans=False
                i+=1
            if ans:
                answer.append(start)

            dic[s[start]]+=1
            if end<lens:
                dic[s[end]]-=1
                        
            start+=1
            end+=1
        return answer