Group Anagrams
给你一个单词列表 strs。如果一个单词可以通过重新排列另一个单词的字母得到，并且每个字母的使用次数都相同，那么这两个单词互为字母异序词。将每个单词与它所有的字母异序词分到一组，并为每组返回一个字符串：将组内的单词按字典序排列，用单个空格连接。各组按照组内第一个单词的字典序排列。
重复的单词在其组内列出两次，没有字母异序词的单词单独成组。字典序是指按字典中的顺序排列：aab 排在 ab 前面，ab 排在 abc 前面。
函数
- strsstring-array
- 要分组的单词，只使用小写字母
- 返回值string-array
- 每组一个字符串：将其中的单词排序后用空格连接，各组按首个单词排序
约束条件
1 ≤ strs.length ≤ 40001 ≤ strs[i].length ≤ 8- 每个单词都只包含小写英文字母。
示例
- 输入
- strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
- 输出
- ["apple", "enlist listen silent", "notes onset stone tones"]
- 解释
enlist、listen和silent都各包含一次 e、i、l、n、s 和 t。notes、onset、stone和tones都包含 e、n、o、s 和 t。apple与其他单词都不匹配，并且按首字母排序时排在前面。
- 输入
- strs = ["race", "arc", "care", "car", "acre"]
- 输出
- ["acre care race", "arc car"]
- 解释
acre、care和race都包含 a、c、e 和 r。arc和car都不包含 e，因此它们单独组成一组。acre排在arc前面，因为第二个字母中 c 排在 r 前面。
- 输入
- strs = ["b", "a", "b"]
- 输出
- ["a", "b b"]
- 解释
b的两个副本互为字母异位词，并且都会留在组中。a没有伙伴，排在最前面。
进阶
如果单词可以包含任意 Unicode 字符，哪种键，无论是排序后的字母还是字母计数，仍然有效？你会如何修改它？
提示
逐个打开提示，每个都会多透露一点。
两个单词只有在包含相同字母且每个字母出现次数相同时，才互为字母重排词。不看其他单词，只根据一个单词，你可以计算出什么，使它的所有字母重排词都得到相同的结果？
把每个单词的字母排序：
listen和silent都会变成eilnst。排序后的形式可作为组名，因此可以用哈希映射将它映射到单词列表，一次遍历就能收集所有分组。先对整个输入进行排序，再对其分组。这样，单词会按字母顺序出现，因此每组的列表本身已经有序，并且每组会在第一个单词出现时创建。用空格连接每个列表。
题解
单独为每个单词计算一个键，使其所有字母异位词的键都相同，而其他单词的键都不同。将单词的字母排序后得到的结果就是这样的键，用一个从键映射到分组的哈希映射即可在一次遍历中收集各组。先对单词排序，就能自然得到所需的顺序。
将每个单词与每个组进行比较
结果正确，但无法在最大的测试中运行完毕
思路
维护一个分组列表，并将每个单词与每组的第一个单词进行比较。字母异位词关系具有传递性，因此每组只需比较一次即可确定单词是否属于该组。两个单词长度相同，且 26 个字母的出现次数都相同，它们就是字母异位词。先对输入排序：这样每组中的单词就会按字母顺序排列，各组也会按首个单词的顺序创建。
如果没有两个单词互为字母异位词，那么每个单词都会与它前面的每个分组进行比较：4000 个单词大约会产生 8 × 10^6 次比较，每次比较最多涉及 8 个字母和 26 个计数器。
算法
- 按字母顺序排列这些单词。
- 对于每个单词，找到首个单词中字母数量相同的组，并将该单词添加到组中。如果没有匹配的组，就新建一个组。
- 按创建顺序返回每组中的单词，每个单词之间用一个空格分隔。
def is_anagram(a, b):
# Same length, and every letter appears as often in a as in b.
if len(a) != len(b):
return False
counts = [0] * 26
for c in a:
counts[ord(c) - 97] += 1
for c in b:
counts[ord(c) - 97] -= 1
return all(x == 0 for x in counts)
def groupAnagrams(strs):
# Sort first: each group fills up in alphabetical order,
# and groups are created in the order of their first word.
groups = []
for word in sorted(strs):
for group in groups:
if is_anagram(group[0], word):
group.append(word)
break
else:
groups.append([word])
return [" ".join(group) for group in groups]在哈希映射中按排序后的字母分组
思路
根据单词本身计算组名。将单词的字母排序后，所有字母异位词都会得到相同的文本：listen、silent 和 enlist 都会变成 eilnst，而 stone 会变成 enost。两个单词的排序结果完全相同，当且仅当它们包含相同数量的相同字母，这就是字母异位词的定义。然后用一个从键映射到单词列表的哈希映射，就能一次遍历将所有单词分组，而且不需要将某个单词与其他组比较。
和之前一样，先对输入排序来确定顺序：每个列表都会按字母顺序填充，并且某个组的第一个单词出现时，对应的键就会加入映射。保留插入顺序的映射会按该顺序返回各组；否则，将各组保存在列表中，并将每个键映射到对应的索引。
对输入排序需要进行大约 5 × 10^4 次单词比较（输入包含 4000 个单词），而不是 8 × 10^6 次。
算法
- 按字母顺序对单词进行排序。
- 对每个单词，将它的字母排序后作为键。
- 在哈希映射中查找这个键。如果它是新的，就为它创建一个空分组，并按创建顺序保留各分组。
- 将单词追加到对应键的分组中。
- 返回每个分组中的单词，每组内用单个空格连接，各分组按创建顺序排列。
def groupAnagrams(strs):
# Sort first: each group fills up in alphabetical order,
# and groups are created in the order of their first word.
groups = {} # key (the letters in sorted order) -> the group's words
for word in sorted(strs):
key = "".join(sorted(word))
groups.setdefault(key, []).append(word)
# A dict keeps insertion order, so the groups come out by first word.
return [" ".join(words) for words in groups.values()]
易错点和边界情况
- 按键而不是按首个单词对各组排序。对于
["cab", "bad"]，键abc和abd会让cab排在前面，但应该由bad排在前面。 - 用集合收集单词。
["b", "a", "b"]必须得到b b；集合只会保留一个副本。 - 键只根据不同的字母构建。
ab和aabb使用相同的两个字母，但它们不是字母异位词。 - 只对每组中的单词排序，却不对输入和各组排序。这样，插入顺序就会跟随输入，而不是首个单词的顺序。
常见问题3
字母异位词分组的时间复杂度是多少？
对于最多包含 k 个字母的 n 个单词，构建排序后的字母键需要 O(n · k log k)，映射处理需要 O(n · k)。对单词排序以确定输出顺序，还需要 O(n · k · log n)，这是主要开销。键和分组需要 O(n · k) 的空间。
字母计数键是否比对每个单词排序更快？
计数键，也就是把 26 个字母的计数写成 1#0#2#… 这样的文本，复杂度是 O(k)，而不是 O(k log k)，因此在处理较长单词时更快。对于不超过 8 个字母的单词，排序同样快。这两种键都很精确：当且仅当两个单词的字母排序后相同时，它们的计数才相同。
为什么不把字母编码的总和用作键呢？
不同的字母组合可能得到相同的总和：a + d 等于 b + c，因此 ad 和 bc 会属于同一组。每个字母对应一个质数，将它们相乘可以得到精确结果，但如果 z 对应 101，十个 z 组成的单词会导致 64 位整数溢出。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def groupAnagrams(strs):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
预期输出
["apple", "enlist listen silent", "notes onset stone tones"]