49_字母异位词分组

类型：字符串

• 49. 字母异位词分组 💛

  https://leetcode-cn.com/problems/group-anagrams/

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

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

  💡 哈希表

  两个字符串互为字母异位词，当且仅当两个字符串包含的字母相同，我们可以根据这一点来将其构建成哈希表的键。使得所有互为异位词的单词都有相同的键。所有互为异位词的单词根据字典排序后，都会变成同一个单词。

  class Solution:
      def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
          mp = collections.defaultdict(list)
  
          for st in strs:
              key = "".join(sorted(st))
              mp[key].append(st)
  
          return list(mp.values())

  时间复杂度：O(n * klog(k))，n 是字符串数量，k 是最长串的长度。空间复杂度：O(nk)