Find All Anagrams in a String#
Problem#
Implementation#
1class Solution:
2 def findAnagrams(self, s: str, p: str) -> List[int]:
3 p_hashmap = self.get_string_hashmap(string=p)
4
5 output: List[int] = []
6
7 window_size: int = len(p)
8
9 len_s = len(s)
10 for index in range(len_s):
11 if index == len_s:
12 break
13
14 substring = s[index:window_size]
15 window_size += 1
16
17 substring_hashmap = self.get_string_hashmap(string=substring)
18
19 if substring_hashmap == p_hashmap:
20 # a match
21 output.append(index)
22 return output
23
24
25 def get_string_hashmap(self, string: str) -> Dict[str, int]:
26 counter = {}
27
28 for char in string:
29 if char not in counter:
30 counter[char] = 1
31 else:
32 counter[char] += 1
33 return counter
Tests#
1s = "cbaebabacd"
2p = "abc"
3expected = [0, 6]
4actual = Solution().findAnagrams(s=s, p=p)
5compare_test_case(actual=actual, expected=expected, description="Test Case 1")
Test passed: Test Case 1