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".
My code:
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
if len(p)>len(s):
return []
record_dict={}
for i in range(len(p)):
if p[i] not in record_dict:
record_dict[p[i]]=1
else:
record_dict[p[i]]+=1
plength=len(p)
i=0
record=[]
tmp_dict={}
while i+plength<len(s)+1:
diff=0
if i==0:
for k in range(plength):
if s[i+k] not in tmp_dict:
tmp_dict[s[i+k]]=1
else:
tmp_dict[s[i+k]]+=1
else:
value=tmp_dict[s[i-1]]
if value==1:
del tmp_dict[s[i-1]]
else:
tmp_dict[s[i-1]]-=1
if s[i+plength-1] not in tmp_dict:
tmp_dict[s[i+plength-1]]=1
else:
tmp_dict[s[i+plength-1]]+=1
#check two dictionary difference
#print(tmp_dict)
if len(tmp_dict)!=len(record_dict):
diff=abs(len(tmp_dict)-len(record_dict))
i+=1
continue
#if have same length, then check
for item in record_dict:
count=record_dict[item]
if item not in tmp_dict:
diff=1
break
else:
count2=tmp_dict[item]
if count!=count2:
diff=1
break
#print(diff)
if diff==0:
record.append(i)
i+=1
else:
i+=diff
return recordSolution: https://leetcode.com/problems/find-all-anagrams-in-a-string/submissions/