Find All Anagrams in a String - LeetCode
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.
Example 1: Input: s = “cbaebabacd”, p = “abc” Output: [0,6] Explanation: The substring with start index = 0 is “cba”, which is an anagram of “abc”. The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2: Input: s = “abab”, p = “ab” Output: [0,1,2] Explanation: The substring with start index = 0 is “ab”, which is an anagram of “ab”. The substring with start index = 1 is “ba”, which is an anagram of “ab”. The substring with start index = 2 is “ab”, which is an anagram of “ab”.
Constraints:
1 <= s.length, p.length <= 3 * 104
s and p consist of lowercase English letters.
- code array #slidingwindow
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
pdic = [0] * 26
for c in p:
pdic[ord(c) - ord('a')] += 1
d = [0] * 26
res = []
for i in range(len(s)):
d[ord(s[i]) - ord('a')] += 1
if i >= len(p) - 1:
if d == pdic: res.append(i-len(p)+1)
d[ord(s[i - len(p) + 1]) - ord('a')] -= 1
return res
- code dic
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
c = dict(Counter(p))
d = defaultdict(int)
res = []
for i in range(len(s)):
d[s[i]] += 1
if i >= len(p) - 1:
if d == c: res.append(i-len(p)+1)
d[s[i - len(p) + 1]] -= 1
if d[s[i - len(p) + 1]] == 0: del d[s[i - len(p) + 1]]
return res