LeetCode02：字母异位词分组

2.字母异位词分组

题目

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

1
2
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

1
2
输入: strs = [""]
输出: [[""]]

示例 3:

1
2
输入: strs = ["a"]
输出: [["a"]]

题解

（1）字母排序

1、首先需要理解什么是字母异位词（相同的字母不同的排列顺序组成的单词）

2、根据特征进行归类，考虑使用哈希表

3、构造单词的字符排序，作为键；分组结果，作为值

1
2
3
4
5
6
7
8
9
10
import collections
class Solution:
    def groupAnagrams(self, strs):
        mp = collections.defaultdict(list)

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

（2）字符计数

1、观察发现，每个字符出现的次数完全相同

2、根据特征进行归类，考虑使用哈希表

3、“#1#3…#0”构造各字母出现次数的特征字符串，作为键；具有相同特征字符串的单词放在一组，作为值

官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
import collections

class Solution:
    def groupAnagrams(self,strs):
        mp = collections.defaultdict(list)
        
        for st in strs:
            counts = [0] *26
            for ch in st:
                counts[ord(ch)-ord("a")] += 1
            # 需要将list转换为tuple才可以进行哈希
            mp[tuple(counts)].append(st)
        return list(mp.values())

我的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def groupAnagrams(self, strs):
        total_dict = {}
        same_map = {}
        res = []
        for index,word in enumerate(strs):
            word_dict = {}
            for s in word:
                word_dict[s] = word_dict.get(s,0) + 1
            total_dict[index] = sorted(word_dict.items())
        for key, val in total_dict.items():
            if tuple(val) not in same_map:
                same_map[tuple(val)] = [key]
            else:
                same_map[tuple(val)].append(key)
        for tar in same_map.values():
            target = [strs[i] for i in tar]
            res.append(target)
        return res

知识点

  • 时间与空间复杂度

1、字母排序：N是单词的个数，K是单词的最大长度。遍历每个单词的时间复杂度是O(N)，对于每个单词的排序时间复杂度为O(Klog(K))。综合以上两点，时间复杂度为O(NKlog(K))。空间上需要O(NK)存储所有单词。

2、字符计数：因为需要遍历每个单词的每个字符，时间复杂度为O(NK)，空间复杂度为O(NK)。

  • defaultdict

collections.defaultdict(list) 是 Python 中 collections 模块提供的一个类，它是字典的一个子类，用于创建默认值为指定类型（这里是列表）的字典。在使用 defaultdict 时，如果访问一个不存在的键，它会自动创建该键，并将其对应的值初始化为指定类型的默认值。

  • ord() 函数

ord() 函数用于返回表示单个字符的 Unicode 字符编码。对于小写字母，ord("a") 返回的是 97，ord("b") 返回的是 98，依此类推。ord(ch) - ord("a")：假设当前字符是小写字母，通过将当前字符的 Unicode 编码减去小写字母 “a” 的 Unicode 编码（即 97），可以得到一个从 0 到 25 的索引值，用来表示该字符在英文字母中的位置，例如 a 对应 0，b 对应 1，依此类推。

  • 字典（dictionary）

在Python中，字典（dictionary）是一种无序的数据类型，用于存储键值对。字典是一种非常灵活和强大的数据结构，常用于存储和操作各种类型的数据。

以下是关于字典的一些常见用法：

  1. 创建字典：

    1
    my_dict = {'A': 100, 'B': 200, 'C': 300}

  2. 添加或更新键值对：

    1
    2
    my_dict['D'] = 400  # 添加新的键值对
    my_dict['A'] = 500  # 更新已有键的值

  3. 访问字典中的元素：

    1
    value = my_dict['A']  # 获取键为'A'的值

  4. 删除键值对：

    1
    del my_dict['B']  # 删除键为'B'的键值对

  5. 遍历字典：

    1
    2
    for key, value in my_dict.items():
        print(key, value)

  6. 检查键是否存在：

    1
    2
    if 'A' in my_dict:
        print('A exists in the dictionary')

  7. 获取所有键或所有值：

    1
    2
    keys = my_dict.keys()  # 获取所有键
    values = my_dict.values()  # 获取所有值

  8. 获取默认值：

    1
    value = my_dict.get('A', 0)  # 获取键'A'的值，如果不存在则返回默认值0

  9. 使用字典推导式创建字典：

    1
    squares = {x: x*x for x in range(1, 6)}  # 创建包含1到5的平方的字典