[LeetCode] 438. Find All Anagrams in a String_Easy

438. Find All Anagrams in a String

DescriptionHintsSubmissionsDiscussSolution

Pick One

---

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

这个题目我最开始的思路是d2 = collections.Counter(p), 然后d1 = collections.Counter(s[:len(p)]), 然后每次往后移动的时候, 就改变相应的d1, 然后比较, 但是发现用Counter比较的时候有个问题, 因为d1 有可能有'c':0 的情况, 虽然跟d2是一样, 但是并不能相等. 所以用[0]*26来代替Counter, 只是比较的时候要用ord(c) - ord('a')去得到index

Code

class Solution:
    def findAnagrams(self, s, p):
        l_s, l_p, ans = len(s), len(p), []
        if l_p > l_s: return ans
        d1, d2 = [0]*26, [0]*26  # 只有小写
        for i in range(l_p):
            d1[ord(s[i]) - ord('a')] += 1
            d2[ord(p[i]) - ord('a')] += 1
        if d1 == d2: ans.append(0)
        for i in range(1, l_s-l_p + 1):
            d1[ord(s[i-1]) - ord('a')] -= 1
            d1[ord(s[i+ l_p -1]) - ord('a')] += 1
            if d1 == d2:
                ans.append(i)
        return ans