lc438. Find All Anagrams in a String

小鱼儿 2022-01-12 01:55 169阅读 0赞

1.  Find All Anagrams in a String Easy

1613

125

Favorite

Share 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".

思路：活动窗口

代码：python3

class Solution:
        def findAnagrams(self, s: str, p: str):
            #活动窗口
            m=len(s)
            n=len(p)
            #边界问题
            if m<n:return []
            shash=[0]*123
            phash=[0]*123
            res=[]
            # for x in s:
            # shash[ord(x)]+=1
            for x in p:
            	phash[ord(x)]+=1
            #窗口
            for i in range(0,m):
                shash[ord(s[i])]+=1
                if i<n:
                    pass
                else:
                    shash[ord(s[i-n])]-=1
                if shash==phash:
                    res.append(i-n+1)
            return res
    复制代码

转载于:https://juejin.im/post/5d0c39d0f265da1bc4145a36