算法: 对位置变换的字符串分组 49. Group Anagrams

49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
1
2

Example 2:

Input: strs = [""]
Output: [[""]]
1
2

Example 3:

Input: strs = ["a"]
Output: [["a"]]
1
2

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

1. 给字母位置进行编码, 分组tuple 对应的位置以及数量

目的是将一组字符串按照它们的字母异位词分组。字母异位词是指由相同字母按不同顺序组成的单词。例如，“eat”, “tea”, “ate” 是一组字母异位词。

import collections
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 初始化一个 defaultdict，其值的类型为 list
        ans = collections.defaultdict(list)
        
        # 遍历输入的字符串列表
        for s in strs:
            # 初始化一个长度为 26 的列表，用于存储每个字母的出现次数
            # 26 是英文字母的数量
            count = [0] * 26
            
            # 遍历字符串中的每个字符
            for c in s:
                # 计算每个字符在字母表中的位置，并更新 count 列表
                count[ord(c) - ord('a')] += 1
            
            # 将 count 列表转换为 tuple 类型，并作为字典的键
            # 将当前字符串添加到对应的列表中
            ans[tuple(count)].append(s)
        
        # 返回字典中的所有值，即分组后的字母异位词
        return ans.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

1. 复杂度分析：
   时间复杂度：O(NK)，其中 N 是字符串的数量，K 是字符串的最大长度。这是因为我们需要遍历每个字符串，并计算每个字符串中每个字母的出现次数。

2. 空间复杂度：O(NK)，主要用于存储输出的结果。

这段代码的核心思想是使用一个固定长度的计数列表来表示每个字符串，该列表中的每个元素都表示字符串中相应字母的出现次数。由于字母异位词具有相同的字母及其出现次数，因此它们会被映射到字典中的同一个键上。最后，字典中的每个值就是一组字母异位词。

在 Python 中，ord() 是一个内置函数，用于返回一个字符（字符串）的 Unicode 码点，即该字符在 Unicode 字符集中的数值表示。ord() 函数的参数是一个表示单个 Unicode 字符的字符串。

例如，ord('a') 会返回 97，因为字符 ‘a’ 在 Unicode 字符集中的码点是 97。同理，ord('b') 会返回 98，ord('1') 会返回 49，等等。

在给定代码中，ord(c) - ord('a') 用于计算字符 c 在字母表中的位置。例如，如果 c 是 ‘a’，那么 ord('a') - ord('a') 的结果是 0，表示 ‘a’ 是字母表中的第一个字母。如果 c 是 ‘b’，那么 ord('b') - ord('a') 的结果是 1，表示 ‘b’ 是字母表中的第二个字母，依此类推。

这种计算方法用于确定在 count 列表中的哪个位置增加字符 c 的计数。例如，如果 c 是 ‘a’，则 count[0] 会增加 1；如果 c 是 ‘b’，则 count[1] 会增加 1，等等。

2. 排序解法

将输入的字符串列表 strs 按照字母异位词进行分组。字母异位词是由相同的字母以不同的顺序组成的单词。例如，“eat”, “tea”, 和 “ate” 是一组字母异位词。

import collections
from typing import List

class Solution(object):
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 初始化一个 defaultdict，其值的类型为 list
        # 这个字典用于存储分组后的字母异位词
        ans = collections.defaultdict(list)
        
        # 遍历输入的字符串列表
        for s in strs:
            # 对每个字符串的字符进行排序，并转换为 tuple 类型
            # 这样，字母异位词会被转换为相同的 tuple
            # 将当前字符串添加到字典中对应的列表中
            ans[tuple(sorted(s))].append(s)
        
        # 返回字典中的所有值，即分组后的字母异位词
        return ans.values()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析：

1. 时间复杂度：O(NKlogK)，其中 N 是字符串的数量，K 是字符串的最大长度。这是因为我们需要遍历每个字符串，并对每个字符串的每个字符进行排序，排序的时间复杂度是 O(KlogK)。

2. 空间复杂度：O(NK)，主要用于存储输出的结果。

这段代码的核心思想是利用字母异位词排序后相等的特性，将排序后的字符串作为字典的键，将原字符串添加到对应的列表中，从而实现分组。最后，字典中的每个值就是一组字母异位词。