LeetCode: 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:

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

Example:

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

Example:

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

问题

给定一个字符串数组 strs，将字谜（Anagrams）组合在一起。你可以以任意顺序返回答案。

字谜是通过重新排列不同单词或短语的字母形成的单词或短语，通常需要使用所有原始字母且只使用一次。

解决方案 1

排序法

Approach 1 / 方法 1

This solution uses sorting as the primary technique to group anagrams. The idea is that two anagrams, when sorted, will result in the same string. By sorting each string and using the sorted string as a key, we can group all anagrams together.

该解决方案使用排序作为主要技术来组合字谜。其思想是，两个字谜在排序后将生成相同的字符串。通过对每个字符串进行排序，并使用排序后的字符串作为键，我们可以将所有字谜组合在一起。

Implementation / 实现

python

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)

        for s in strs:
            sorted_str = ''.join(sorted(s))
            anagrams[sorted_str].append(s)

        return list(anagrams.values())

Explanation / 解释

1. Initialize the Anagrams Dictionary / 初始化字谜字典

   anagrams = defaultdict(list)

   • English: We initialize a dictionary anagrams where each key is a sorted string, and the corresponding value is a list of anagrams.
   • Chinese: 我们初始化一个字典 anagrams，其中每个键是一个排序后的字符串，对应的值是字谜的列表。

2. Iterate Over Each String / 遍历每个字符串

   for s in strs:

   • English: We iterate over each string s in the input list strs.
   • Chinese: 我们遍历输入列表 strs 中的每个字符串 s。

3. Sort the String / 对字符串进行排序

   sorted_str = ''.join(sorted(s))

   • English: We sort the string s and convert it back to a string sorted_str.
   • Chinese: 我们对字符串 s 进行排序，并将其转换回一个字符串 sorted_str。

4. Group the Anagrams / 组合字谜

   anagrams[sorted_str].append(s)

   • English: We use the sorted string as the key in the anagrams dictionary and append the original string s to the corresponding list.
   • Chinese: 我们使用排序后的字符串作为 anagrams 字典中的键，并将原始字符串 s 添加到对应的列表中。

5. Return the Grouped Anagrams / 返回组合后的字谜

   return list(anagrams.values())

   • English: Finally, we return the values of the anagrams dictionary, which are the grouped anagrams.
   • Chinese: 最后，我们返回 anagrams 字典的值，即组合后的字谜。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n k log k), where n is the number of strings, and k is the maximum length of a string. The sorting operation for each string takes O(k * log k) time.
• Space Complexity / 空间复杂度: O(n * k), where n is the number of strings, and k is the maximum length of a string. The space is used for storing the grouped anagrams.

Key Concept / 关键概念

• Sorting / 排序: By sorting each string, anagrams can be easily identified because they will have the same sorted string.
• 排序: 通过对每个字符串进行排序，可以轻松识别字谜，因为它们将具有相同的排序后的字符串。

解决方案 2

字符计数法

Approach 2 / 方法 2

Another approach is to use character counts as a way to group anagrams. Instead of sorting the string, we count the frequency of each character and use this count as the key. This approach is particularly useful when dealing with large strings where sorting might be expensive.

另一种方法是使用字符计数来组合字谜。我们不对字符串进行排序，而是计算每个字符的频率，并将此计数作为键。当处理可能导致排序开销较大的长字符串时，此方法尤为有用。

Implementation / 实现

python

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)

        for s in strs:
            count = [0] * 26  # Initialize count of 26 letters

            for char in s:
                count[ord(char) - ord('a')] += 1

            anagrams[tuple(count)].append(s)

        return list(anagrams.values())

Explanation / 解释

1. Initialize the Anagrams Dictionary / 初始化字谜字典

   anagrams = defaultdict(list)

   • English: We initialize a dictionary anagrams where each key is a tuple representing the character count, and the corresponding value is a list of anagrams.
   • Chinese: 我们初始化一个字典 anagrams，其中每个键是表示字符计数的元组，对应的值是字谜的列表。

2. Iterate Over Each String / 遍历每个字符串

   for s in strs:

   • English: We iterate over each string s in the input list strs.
   • Chinese: 我们遍历输入列表 strs 中的每个字符串 s。

3. Count Characters in the String / 计算字符串中的字符

   count = [0] * 26
   for char in s:
      count[ord(char) - ord('a')] += 1

   • English: We count the frequency of each character in the string and store it in a list count of size 26 (for each letter in the alphabet).
   • Chinese: 我们计算字符串中每个字符的频率，并将其存储在大小为26（对应字母表中每个字母）的列表 count 中。

4. Group the Anagrams / 组合字谜

   anagrams[tuple(count)].append(s)

   • English: We convert the count list into a tuple and use it as a key in the anagrams dictionary, appending the original string s to the corresponding list.
   • Chinese: 我们将 count 列表转换为元组，并将其作为 anagrams 字典中的键，将原始字符串 s 添加到对应的列表中。

5. Return the Grouped Anagrams / 返回组合后的字谜

   return list(anagrams.values())

   • English: Finally, we return the values of the anagrams dictionary, which are the grouped anagrams.
   • Chinese: 最后，我们返回 anagrams 字典的值，即组合后的字谜。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n * k), where n is the number of strings, and k is the maximum length of a string. The character count operation for each string takes O(k) time.
• Space Complexity / 空间复杂度: O(n * k), where n is the number of strings, and k is the maximum length of a string. The space is used for storing the grouped anagrams.

Key Concept / 关键概念

• Character Counting / 字符计数: This approach groups anagrams by counting the frequency of each character, making it a powerful tool when sorting is too costly.
• 字符计数: 这种方法通过计算每个字符的频率来组合字谜，当排序代价太高时，它是一种强大的工具。

Summary / 总结

• English: Both sorting and character counting approaches are effective for grouping anagrams. Sorting is more straightforward, while character counting is more optimized for performance in certain cases.

• Chinese: 排序和字符计数方法都可以有效地组合字谜。排序更直接，而字符计数在某些情况下则更优化。

Tips / 提示

• English: Use the character counting approach when dealing with longer strings or when sorting might be inefficient.
• Chinese: 当处理较长的字符串或排序可能效率较低时，使用字符计数方法。

Solution Template for Similar Questions / 提示

• English: Consider both sorting and character counting approaches for problems involving grouping based on string properties.
• Chinese: 对于基于字符串属性进行分组的问题，考虑排序和字符计数方法。

5 More Similar Questions / 推荐5问题

1. LeetCode 242. Valid Anagram
2. LeetCode 438. Find All Anagrams in a String
3. LeetCode 14. Longest Common Prefix
4. LeetCode 49. Group Anagrams
5. LeetCode 647. Palindromic Substrings

Recommended Resources / 推荐资源

• English: Practice both sorting and character counting methods on similar problems to solidify your understanding and enhance your problem-solving skills.
• Chinese: 在类似问题上练习排序和字符计数方法，以巩固理解并提高问题解决能力。

Group Anagrams – Categorize Strings by Count – Leetcode 49 by NeetCode