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