异位构词

定义

如果对调字符，使得单词 w 变成单词 v，那么 w 就是 v 的异位构词。假设有一个集合包含了 n 个最大长度为 k 的单词，现在要找到所有的异位构词。

输入：
le chien marche vers sa niche et trouve une limace de chine nue pleine de malice qui lui fait du charme

输出：
{une nue}, {marche charme}, {chien chine niche}, {malice limace}.

算法思路：

算法的思路是计算每个单词的签名。两个单词能得到相同的签名，当且仅当他们互为异位构词。这个签名不过是包含了相同字母的另一个单词，是把要计算签名的单词中所有字母按顺序排列后得到的。

算法使用的数据结构是一个字典，将每个签名与拥有这个签名的所有单词的列表对应起来。

def anagrams(words):                     # words 为单词列表
    words = list(set(words))             # 删除重复项
    d = dict()                           # 保存有同样签名的单词
    for i in range(len(words)):
        s = ''.join(sorted(words[i]))    # 签名
        if s in d:
            d[s].append(i)
        else:
            d[s] = [i]
    ans = []
    for s in d:
        if len(d[s]) > 1:                 #  保存所有拥有异位构词的结果
            ans.append([words[i] for i in d[s]])
    return ans