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".
Solution
使用count dict的方式加sliding window 可解 (超出len(p)式dict对于1st char count -1
Time complexity O(len(s)+len(p)
Space complexity O(len(s)+len(p)
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
res=[]
count = [0]*26
for c in p:
count[ord(c)-ord('a')] +=1
count_s = [0]*26
l = 0
for i in range(len(s)):
if l < len(p):
count_s[ord(s[i])-ord('a')] += 1
l += 1
if l == len(p):
if count == count_s:
res.append(i-l+1)
count_s[ord(s[i-l+1])-ord('a')] -= 1
l -=1
return res
Leetcode 242 easy同样方法
使用sort的方法会超时！
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
res=[]
p_order = sorted(p)
for i in range(len(s)-len(p)+1):
s_order = s[i:i+len(p)]
s_order = sorted(s_order)
if s_order == p_order:
res.append(i)
return res
