LeetCode

Appearance

438.Find All Anagrams in a String ​

题目 ​

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

 

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

 

Constraints:

  • 1 <= s.length, p.length <= 3 * 104
  • s and p consist of lowercase English letters.
Related Topics
  • 哈希表
  • 字符串
  • 滑动窗口

  • 👍 1681
  • 👎 0

    • 思路 ​

    滑动窗口，固定窗口size尺寸系列

    • expand 时机： char in needs
    • shrink 时机： right - left + 1 >= len(target)

    解法 ​

    py
    from collections import defaultdict
from typing import List

# leetcode submit region begin(Prohibit modification and deletion)

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        window = defaultdict(int)
        needs = defaultdict(int)
        res = []
        for i in p:
            needs[i] += 1

        left = right = 0

        for right, char in enumerate(s):
            if char in needs:
                window[char] += 1

            if window == needs:
                res.append(left)

            if right - left + 1 >= len(p):
                remove_char = s[left]
                if remove_char in window:
                    window[remove_char] -= 1
                    if window[remove_char] == 0:
                        del window[remove_char]
                left += 1

        return res
# leetcode submit region end(Prohibit modification and deletion)

Solution().findAnagrams('cbaebabacd', 'abc')

    复杂度分析 ​

    • 时间复杂度O(N)
      • N = len(s) + len(p)
    • 空间复杂度O(1)
      • 创建 hashmap 的最大内存消耗为 26 * 2 为一个常数