【LeetCode刷题笔记（2）】【Python】【字母异位词分组】【中等】

字母异位词分组

题目描述

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

• 输入：字符串数组strs

• 输出：结果列表

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

要求：

• 可以按任意顺序返回答案。

示例：

• 输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
• 输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

---

• 输入: strs = [“”]
• 输出: [[“”]]

---

• 输入: strs = [“a”]
• 输出: [[“a”]]

---

提示：

• 1 <= strs.length <= 10⁴
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

解决方案：哈希表 + 字符串排序

【哈希表】是一种非常高效的数据结构，它通过哈希函数将键映射到值上。哈希表的优点是查找速度快，因为可以通过哈希函数快速计算出对应键的值的位置。

因此，哈希表非常适合处理字母异位词分组问题，因为它能够快速地查找和存储数据（该问题涉及查找和存储）。

---

问题1：那么具体如何实现呢？

在python中，字典对象的底层实现是基于哈希表。==> 用字典作为哈希表存储字母异位词

问题2：在python字典对象中，键是唯一的，但在多个互为字母异位词的字符串中，什么是唯一的？

这些字符串的排序结果是唯一的！===> 哈希表的【键】可定义为字母异位词的排序结果，哈希表的【值】可用列表对象依次存储互为字母异位词且这些词的排序结果正好为键的字符串！

想清楚这两个关键问题，代码也就简单了：

class Solution:
    def groupAnagrams(self, strs):  
        """  
        :type strs: List[str]  
        :rtype: List[List[str]]  
        """  
        # 创建一个空的哈希表  
        anagram_groups = {}  
        
        # 遍历给定的字符串列表  
        for word in strs:  
            # 对当前字符串进行排序，作为哈希表的键  
            sorted_word = ''.join(sorted(word))  
            
            # 以【排序后的字符串】作为键，以【列表】存放【原始字符串】作为值
            # 如果哈希表中没有这个键，就创建一个新的键值对
            if sorted_word not in anagram_groups:  
                anagram_groups[sorted_word] = [word]  
            else:  
                # 否则，将当前单词添加到对应的列表中  
                anagram_groups[sorted_word].append(word)  
                
        # 将哈希表的所有值以列表形式存储，并返回结果  
        return list(anagram_groups.values())

运行结果

复杂度分析

• 时间复杂度：O(N K log K)，其中 N 是 strs 中的字符串的数量，K 是 strs 中的字符串的最大长度。

  • 需要遍历整个字符串 ===> O(N)
  • 每次遍历，极端情况下需要对最长字符串排序 ==> O(K log K)
  • 总时间复杂度 ===> O(N K log K)

• 空间复杂度：O(N K)

  • 需要用哈希表存储全部字符串

题外话

回到问题二，对于互为字母异位词的字符串，除了排序结果是唯一的，还有什么也是唯一的吗？

相同字母出现的次数一定是相同的，即也是唯一的！===> 感兴趣的读者也可以尝试将每个字母出现的次数使用字符串表示，作为哈希表的键；

结束语

• 亲爱的读者，感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见，因此在这里鼓励您对我们的博客进行评论。
• 您的建议和看法对我们来说非常重要，这有助于我们更好地了解您的需求，并提供更高质量的内容和服务。
• 无论您是喜欢我们的博客还是对其有任何疑问或建议，我们都非常期待您的留言。让我们一起互动，共同进步！谢谢您的支持和参与！
• 我会坚持不懈地创作，并持续优化博文质量，为您提供更好的阅读体验。
• 谢谢您的阅读！