438 Find All Anagrams in a String
438. Find All Anagrams in a String
题目: https://leetcode.com/problems/Find-All-Anagrams-in-a-String/
难度:
Easy
思路
刚开始打算直接遍历整个s，时间复杂度为O(m*n),m和n分别为字符串p和s的长度，但是超时了
class Solution(object): # 此法超时
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
l, res = len(p), []
for i in range(len(s)):
if collections.Counter(s[i:i+l]) == collections.Counter(p):
res.append(i)
return res
于是用双指针，left和right都从0开始往后遍历
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
res, cnts = [], [0] * 26
for c in p:
cnts[ord(c) - ord('a')] += 1
left, right = 0, 0
while right < len(s):
cnts[ord(s[right]) - ord('a')] -= 1
while left <= right and cnts[ord(s[right]) - ord('a')] < 0:
cnts[ord(s[left]) - ord('a')] += 1
left += 1
if right - left + 1 == len(p):
res.append(left)
right += 1
return res
模板大法好
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
res = []
if len(p) > len(s):
return res
maps = collections.Counter(p)
counter = len(maps.keys())
begin, end, head, length = 0, 0, 0, sys.maxint
while end < len(s):
if s[end] in maps:
maps[s[end]] -= 1
if maps[s[end]] == 0:
counter -= 1
end += 1
while counter == 0:
if s[begin] in maps:
maps[s[begin]] += 1
if maps[s[begin]] > 0:
counter += 1
if end - begin == len(p):
res.append(begin)
begin += 1
return res
