wbfwonderful's Blog
【代码随想录】哈希表1
wbfwonderful Lv4
  2025-06-30 21:52:59   2025-07-01 15:33:38    1.4k 字  6 分钟  

Python 哈希表相关操作

哈希表都是用来快速判断一个元素是否出现集合里。例如要查询一个名字是否在这所学校里。要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。

list

dict

defaultdict 和 Counter

这两个类都是 dict 的子类，在 key 不存在时，dict 会报错。但是这两个类定义了 __missing__() 方法，在 key 不存在时，会调用该方法并返回其值。例如，Counter 类的定义如下，即 key 不存在的话就返回 0，满足计数器的要求。

1
2
3
class Counter(dict):
    def __missing__(self, key):
        return 0

defaultdict 则会返回初始化时给定的类型。例如：

1
2
3
d = defaultdict(int)

d = defaultdict(list)

使用 dict 也可以实现 Counter 类似的效果：

1
2
3
d = dict()

d[key] = d.get(key, 0) + 1

set

集合中的元素不可重复，可以遍历，但不能使用索引来访问。

添加元素：add()

删除元素：remove()

242. 有效的字母异位词

题目链接 link

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:

输入: s = “rat”, t = “car”
输出: false

思路

分别记录两个字符串中各个字符的数量，然后判断是否相等。

数组写法

使用相对的 ASCII 来作为索引。这里使用了 ord 方法，用于将字符转换为数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_list = [0 for _ in range(26)]
        for i in s:
            index = ord(i) - ord('a')
            s_list[index] += 1
        
        for i in t:
            index = ord(i) - ord('a')
            s_list[index] -= 1
        
        for i in s_list:
            if i != 0:
                return False
        
        return True

字典写法

注意需要使用 get(i, 0) 方法，如果没有对应的键值，则返回 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = {}
        for i in s:
            record[i] = record.get(i, 0) + 1
        
        for i in t:
            record[i] = record.get(i, 0) - 1
        
        for i in record:
            if record[i] != 0:
                return False
        
        return True

Counter 写法

可以直接比较两个 Counter（计数器 dict）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record_s = Counter()
        record_t = Counter()
        for i in s:
            record_s[i] += 1
        
        for i in t:
            record_t[i] += 1
        
        if record_s == record_t:
            return True
        else:
            return False

49. 字母异位词分组

题目链接 link

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
解释：
在 strs 中没有字符串可以通过重新排列来形成 “bat”。
字符串 “nat” 和 “tan” 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 “ate” ，”eat” 和 “tea” 是字母异位词，因为它们可以重新排列以形成彼此。

思路 1

遍历所有的字符串，判断该字符串是否和已经分好组的字符串为字母异位词，如果是，则添加到满足的那个组，如果不是则单独添加为一个组。但是这段代码会超出时间限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def judge(self, s, t):
        record_s = Counter()
        record_t = Counter()
        for i in s:
            record_s[i] += 1
        
        for i in t:
            record_t[i] += 1
        
        if record_s == record_t:
            return True
        else:
            return False

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = []

        for s in strs:
            if len(res) == 0:
                res.append([s])
            else:
                flag = False
                for index in range(len(res)):
                    if self.judge(s, res[index][0]):
                        res[index].append(s)
                        flag = True
                        break
                if flag == False:
                    res.append([s])
        
        return res

思路 2

思路 1 的时间复杂度为 O(n*n*n)，优化的点在于判断是否为字母异位词时，可以将字符串进行排序，将排序后的字符串作为 key，将对应的字符串存在一个 list 中 作为 value。这里需要用到 defaultdict。当访问一个不存在的键时，defaultdict 会自动调用 default_factory 生成一个默认值并插入字典，然后返回这个值。

这里使用了 sorted 方法，可以将任意可迭代的对象进行排序，返回一个 list。

1
2
3
4
5
6
7
8
9
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)

        for s in strs:
            key = "".join(sorted(s))
            d[key].append(s)
        
        return list(d.values())

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

link

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

思路

滑动窗口，对于每一个字串都进行判断。有如下优化：

  • 如果当前字串是字母异位词，则只需要比较当前窗口出去的字符和进来的字符是否相等，如果相等则下一个字串也为字母异位词。
  • 判断字母异位词直接使用排序，时间复杂度为 O(klogk)，否则为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:

    def judge(self, s, t):
        ss = "".join(sorted(s))
        tt = "".join(sorted(t))

        if ss == tt:
            return True
        else:
            return False      

    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        pre = None
        for start in range(len(s) - len(p) + 1):
            end = start + len(p)
            if pre == None:
                if self.judge(s[start:end], p):
                    res.append(start)
                    pre = s[start]
            else:
                if pre == s[end - 1]:
                    res.append(start)
                    pre = s[start]
                else:
                    pre = None
        return res

思路 2

对于每个字串，不用每次都进行判断，只需要记录每个字符的数量以及其变化情况即可。

【代码随想录】哈希表1
Leetcode/hash1/
作者
wbfwonderful
发布于
2025-06-30 21:52
许可
  1. 1. Python 哈希表相关操作
    1. 1.1. list
    2. 1.2. dict
      1. 1.2.1. defaultdict 和 Counter
    3. 1.3. set
  2. 2. 242. 有效的字母异位词
    1. 2.1. 思路
      1. 2.1.1. 数组写法
      2. 2.1.2. 字典写法
      3. 2.1.3. Counter 写法
  3. 3. 49. 字母异位词分组
    1. 3.1. 思路 1
    2. 3.2. 思路 2
  4. 4. 438. 找到字符串中所有字母异位词
    1. 4.1. 思路
    2. 4.2. 思路 2
  1. 1. Python 哈希表相关操作
    1. 1.1. list
    2. 1.2. dict
      1. 1.2.1. defaultdict 和 Counter
    3. 1.3. set
  2. 2. 242. 有效的字母异位词
    1. 2.1. 思路
      1. 2.1.1. 数组写法
      2. 2.1.2. 字典写法
      3. 2.1.3. Counter 写法
  3. 3. 49. 字母异位词分组
    1. 3.1. 思路 1
    2. 3.2. 思路 2
  4. 4. 438. 找到字符串中所有字母异位词
    1. 4.1. 思路
    2. 4.2. 思路 2