anagram 变位词题目一则

转载请注明出处：https://blog.csdn.net/jpch89/article/details/85063226

1. 题目

Given an array of strings, return an array of strings that groups all anagrams.
An anagram is a word that has the same letters, but in different positions.
i.e. given [\"cars\", \"thing\", \"scar\", \"dog\", \"god\", \"arcs\", \"the\"]
return [[\"cars\", \"scar\", \"arcs\"], [\"thing\"], [\"dog\", \"god\"], [\"the\"]]

2. 思路

对每个单词的所有字母进行排序，得到的值可以作为字典的键。
比如 scar 和 cars 得到的键是 acrs。
与键对应的值是一个列表，存储原单词。
返回这个字典的值组成的列表即可。

3. 实现

def find_anagrams(words):
    words_pair = zip(words, [str(sorted(w)) for w in words])
    res_dict = {}
    for i, j in words_pair:
        res_dict.setdefault(j, [])
        res_dict[j].append(i)
    return [i for i in res_dict.values()]


words = [\'cars\', \'thing\', \'scar\', \'dog\', \'god\', \'arcs\', \'the\']
res = find_anagrams(words)
print(res)

\"\"\"
[[\'cars\', \'scar\', \'arcs\'], [\'thing\'], [\'dog\', \'god\'], [\'the\']]
\"\"\"

完成于 2018.12.18