Find All Anagrams in a String – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem – Find All Anagrams in a String – Leetcode Challenge – Python Solution.
Source – qiyuangong’s repository.
class Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ res = [] if s is None or p is None or len(s) == 0 or len(p) == 0: return res char_map = [0] * 256 for c in p: char_map[ord(c)] += 1 left, right, count = 0, 0, len(p) while right < len(s): if char_map[ord(s[right])] >= 1: count -= 1 char_map[ord(s[right])] -= 1 right += 1 if count == 0: res.append(left) if right - left == len(p): if char_map[ord(s[left])] >= 0: count += 1 char_map[ord(s[left])] += 1 left += 1 return res # def findAnagrams(self, s, p): # if len(s) < len(p): # return [] # res = [] # p_len = len(p) # bit_map = [] # for _ in range(26): # bit_map.append(0) # for c in p: # bit_map[ord(c) - ord('a')] += 1 # s_p = str(bit_map) # for i in range(26): # bit_map[i] = 0 # for i in range(p_len - 1): # bit_map[ord(s[i]) - ord('a')] += 1 # for i in range(p_len - 1, len(s)): # bit_map[ord(s[i]) - ord('a')] += 1 # if i - p_len >= 0: # bit_map[ord(s[i - p_len]) - ord('a')] -= 1 # if str(bit_map) == s_p: # res.append(i - p_len + 1) # return res # def findAnagrams(self, s, p): # """ # :type s: str # :type p: str # :rtype: List[int] # """ # res = [] # pCounter = collections.Counter(p) # sCounter = collections.Counter(s[:len(p)-1]) # for i in range(len(p)-1,len(s)): # sCounter[s[i]] += 1 # include a new char in the char_map # if sCounter == pCounter: # This step is O(1), since there are at most 26 English letters # res.append(i-len(p)+1) # append the starting index # sCounter[s[i-len(p)+1]] -= 1 # decrease the count of oldest char in the window # if sCounter[s[i-len(p)+1]] == 0: # del sCounter[s[i-len(p)+1]] # remove the count if it is 0 # return res