「力扣」第 49 题:字母异位词分组(哈希表)

liweiwei1419 ... 2021-12-26 哈希表
  • 哈希表
  • 滚动哈希
About 5 min

视频讲解

📺 这道题在 B 站 (opens new window) 可以收看视频讲解,可以点击下面的视频右上角「去 bilibili 观看」,选择快速播放,获得更好的观看体验。

发布在「算法吧」的视频(带字幕和进度条):

# 题目描述

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]。
输出:[["ate","eat","tea"],["nat","tan"],["bat"]]。
说明:1、所有输入均为小写字母。2、不考虑答案输出的顺序。
1
2
3

参考代码

class Solution:
    def groupAnagrams(self, strs):
        map = dict()

        if len(strs) == 0:
            return []

        for s in strs:
            key = ''.join(sorted(list(s)))
            if key not in map:
                map[key] = [s]
            else:
                map[key].append(s)

        return list(map.values())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

思路:

  • 每个字符串其实对应一个 key,相同字母组合对应的 key 是相等的。这里考察了哈希函数。

这篇题解不是很严谨,可以这么做是我尝试出来的,限于本人对这个知识点的理解有限,思路没有办法说得很清楚,也没有办法证明给大家看,只能说是思路通过测试得到验证。

大家直接看代码,或者看这个题解评论区置顶的评论,有朋友提到证明部分。

有哈希表的基础知识,是很容易想到思路的。这里「哈希」是 hash 的音译,意译是「散列」。

思路

  • 分入一组的字符串的特征:字符以及字符的个数相等,但是顺序不同;
  • 这样的特征其实可以做一个映射,思想来源于哈希规则。这里要去除顺序的影响,那么我们就只关心每个字符以及它出现的次数;
  • 每个字符对应一个 ASCII 值,用 ASCII 值乘以字符出现的次数的和感觉上就能表征一组字符串,但是很容易想到,这里面会有重复的值;
  • 一个替代的做法是,把 ASCII 值 替换成为质数,于是这些数值一定不会有公约数,不在一组的数,它们的和一定不相等(也就是放在哈希表里,肯定不会被分在一个桶里);
  • 所有输入均为小写字母,因此只需要做 26 个映射,这种映射可以通过数组实现。

评论有朋友提到,这样计算出来的「哈希值」是有可能整型越界的,这一点是我一开始没有想到的。但是仔细算了一下,这里「消耗」最大的值就是字母 z ,它对应的 ASCII 码是 25(已经减去了偏移),它对应的质数最大是 101,如果全部使用 z 是最消耗值的,运行下面这段代码:

System.out.println(Integer.MAX_VALUE / 101 / 25);
1

输出:850488。

因此,要产生溢出,输入字符至少长度要达到 850488 才可以。在这里认为不存在这种测试用例。

知识点复习:

  • 哈希表的底层就是数组;
  • 哈希函数;
  • 哈希冲突的解决办法:1、链接法;2、开放地址法;
  • 哈希表的扩容。

参考《算法导论》或者《算法 4》,初学的时候懂得意思,有个感性认知即可。

参考代码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {

    public List<List<String>> groupAnagrams(String[] strs) {
        // 考察了哈希函数的基本知识,只要 26 个即可
        // (小写字母ACSII 码 - 97 )以后和质数的对应规则,这个数组的元素顺序无所谓
        // key 是下标,value 就是数值
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
                73, 79, 83, 89, 97, 101};

        long mod = 1000000000 + 7;

        // key 是字符串自定义规则下的哈希值
        Map<Long, List<String>> hashMap = new HashMap<>();
        for (String s : strs) {
            long hashValue = 1;

            char[] charArray = s.toCharArray();
            for (char c : charArray) {
                hashValue = ((hashValue % mod) * (primes[c - 'a'] % mod)) % mod;
            }

            if (hashMap.containsKey(hashValue)) {
                List<String> curList = hashMap.get(hashValue);
                curList.add(s);
            } else {
                List<String> newList = new ArrayList<>();
                newList.add(s);

                hashMap.put(hashValue, newList);
            }
        }
        return new ArrayList<>(hashMap.values());
    }
}
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
33
34
35
36
37
38
39
40
Last update: May 2, 2022 13:22
Contributors: liweiwei1419