题目

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

    方案一（使用元祖为键(0, 0, 0, …)）

  1. class Solution:
  2.     def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
  3.         d = {} # key 为字符元祖，每个位置代表一个字符，value 为对应的词列表
  4.         for s in strs:
  5.             word = [0] * 26
  6.             for ch in s:
  7.                 word[ord(ch) - 97] += 1
  9.             t = tuple(word)
  10.             if t not in d:
  11.                 d[t] = []
  12.             d[t].append(s)
  14.         return [value for value in d.values()]
  • 挑选键的时候我优先想到的是 ascii 的乘积和 加和，但是最终发现会出现冲突；
  • 然后想到的就是使用元祖，因为字母异位词只需要保证每个字符出现次数相同即可。

    leetcode相同方案但是性能较好的实现

  1. class Solution:
  2.     def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
  3.         ans = collections.defaultdict(list)
  4.         for s in strs:
  5.             ans[tuple(sorted(s))].append(s)
  6.         return list(ans.values())

方案二（使用排序后的字符串作为键）

  1. class Solution:
  2.     def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
  3.         t_dict={}
  4.         for t_str in strs:
  5.             sort_str=self.hashMapFun(t_str)
  6.             if sort_str not in t_dict:
  7.                 t_dict[sort_str] = []
  8.             t_dict[sort_str].append(t_str)
  10.         return list(t_dict.values())
  11.     def hashMapFun(self,strings):
  12.         return "".join(sorted(list(strings)))

原文

https://leetcode-cn.com/explore/orignial/card/all-about-lockup-table/239/learn-to-use-keys/999/