LeetCode

Posted on | In | 0 comments |

Array

438. Find All Anagrams in a String

题目描述:

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

解题思路: 滑窗法

  • 最简单的思路是首先对 p 排序, 然后对 s 滑窗中的字符进行排序, 然后比较;
  • 进一步地, 使用 Counter 统计 p 中字符出现的次数, 在滑窗过程中统计滑窗中字符个数, 然后比较两个字典是否相等;
  • 再进一步, 滑动窗口每前进一个字符, 必然有部分字符已经统计, 因而无需重复统计, 只需滑窗最前一个字符的键值减 1, 滑窗后一个字符加 1, 维持这个滑窗并比较.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findAnagrams_optimal(self, s, p):
        res = []
        pCounter = Counter(p)
        sCounter = Counter(s[:len_p - 1])
        for i in range(len(p) - 1, len(s)):
            sCounter[s[i]] += 1             # include a new char in the window

            start = i - len(p) + 1
            if sCounter == pCounter:        # This step is O(1), since there are at most 26 English letters
                res.append(start)           # append the starting index

            sCounter[s[start]] -= 1         # decrease the count of oldest char in the window
            if sCounter[s[start]] == 0:
                del sCounter[s[start]]      # remove the count if it is 0
        return res