PeterQwQ
0%

Leetcode 438 找到字符串中所有字母异位词

发表于 更新于

给定两个非空字符串 s 和 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

一开始写了暴力，也能过但是太慢了：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        length_s = len(s)
        length_p = len(p)
        sorted_p = ''.join(sorted(p))
        ans = []
        for i in range(length_s-length_p+1):
            now_str = ''.join(sorted(s[i:i+length_p]))
            if now_str == sorted_p:
                ans.append(i)
        return ans

后来观察这道题，其实只需要存储字母数量然后再滑动窗口就行了，因为如果是字母异位词，那么他们的字母数量是一样的，可以左右指针滑动窗口，然后比较两个字典是否相等：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:    
        n_s, n_p = len(s), len(p)
        if n_s < n_p:
            return []
        ans = []
        hash_table_p = {}
        hash_table_current = {}
        for i in range(n_p):
            hash_table_p[p[i]] = hash_table_p.get(p[i], 0) + 1
            hash_table_current[s[i]] = hash_table_current.get(s[i], 0) + 1
        for i in range(n_s-n_p+1):
            right = n_p+i
            if hash_table_p == hash_table_current:
                ans.append(i)
            hash_table_current[s[i]] -= 1
            if hash_table_current[s[i]] == 0:
                del hash_table_current[s[i]]
            if right != n_s:
                hash_table_current[s[right]] = hash_table_current.get(s[right], 0) + 1
            else:
                break
        return ans