Description
Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
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".
Solutions
1. Brute Force
# Time: O(nm)
# Space: O(n)
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ns, np = len(s), len(p)
res = []
for i in range(ns-np+1):
if self.is_anagrams(s[i:i+np], p):
res.append(i)
return res
def is_anagrams(self, s, p):
s_dict = collections.defaultdict()
p_dict = collections.defaultdict()
for ch in s:
s_dict[ch] = s_dict.get(ch, 0) + 1
for ch in p:
p_dict[ch] = p_dict.get(ch, 0) + 1
return s_dict == p_dict
# Time Limit Exceeded
# 34/36 cases passed (N/A)
# Time: O(nm)
# Space: O(n)
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ns, np = len(s), len(p)
p_dict = collections.defaultdict()
for ch in p:
p_dict[ch] = p_dict.get(ch, 0) + 1
res = []
for i in range(ns-np+1):
s_dict = collections.defaultdict()
for j in range(i, i+np):
s_dict[s[j]] = s_dict.get(s[j], 0) + 1
if s_dict == p_dict:
res.append(i)
else:
s_dict[s[i]] = s_dict[s[i]] - 1
if s_dict[s[i]] == 0:
s_dict.pop(s[i])
return res
# Time Limit Exceeded
# 34/36 cases passed (N/A)
2. Hash Table
用字符串的机器码作为下标，定义一个足够大的数组，Python 中 123 即可。
# Time: O(n)
# Space: O(1)
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ns, np = len(s), len(p)
if np > ns:
return []
shash, phash = [0] * 123, [0] * 123
res = []
for ch in p:
phash[ord(ch)] += 1
for i in range(np-1):
shash[ord(s[i])] += 1
for i in range(np-1, ns):
shash[ord(s[i])] += 1
if i - np >= 0:
shash[ord(s[i - np])] -= 1
if shash == phash:
res.append(i - np + 1)
return res
# 36/36 cases passed (112 ms)
# Your runtime beats 75.49 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.7 MB)