使用Python查找一组单词的字谜

Question

假设我有一个字符串列表，比如 ["car", "tree", "boy", "girl", "arc"] 之类的。我想在这个列表中找到字母异位词的组合，比如 (car, arc)。

我尝试写代码来遍历这个列表，并比较字符串的对，但我该怎么处理字母顺序不同的情况呢？

---

_{如果你只想检查一对字符串是否是字母异位词，可以参考这个链接：检查字符串是否相互为字母异位词。}

Answer 1

这个问题有好几种解决方法：

1. 经典方法

   首先，我们要了解什么是变位词：如果两个单词由相同的字母组成，并且每个字母在这两个单词中出现的次数完全相同，那么这两个单词就是变位词。这其实就是每个单词中字母出现次数的统计。我们可以用 collections.Counter 这个数据结构来处理这个问题（查看文档）。具体的步骤如下：

   • 建立一个字典，字典的键是字母统计，值是具有相同字母统计的单词列表。
   • 对每个单词进行字母统计，并把它添加到对应的字母统计列表中。
   • 输出字典中的值列表。

   下面是代码：

   from collections import Counter, defaultdict
   
   def anagram(words):
       anagrams = defaultdict(list)
       for word in words:
           histogram = tuple(Counter(word).items()) # build a hashable histogram
           anagrams[histogram].append(word)
       return list(anagrams.values())
   
   keywords = ("hi", "hello", "bye", "helol", "abc", "cab", 
                   "bac", "silenced", "licensed", "declines")
   
   print(anagram(keywords))
   

   需要注意的是，构建 Counter 的时间复杂度是 O(l)，而对每个单词进行排序的时间复杂度是 O(n*log(l))，其中 l 是单词的长度。

2. 使用质数解决变位词问题

   这是一个更高级的解决方案，依赖于质数的“乘法唯一性”。你可以参考这个 StackOverflow 的帖子：使用质数比较变位词，以及 这里有一个 Python 实现的示例。

Answer 2

创建一个字典，里面的内容是（排序后的单词，单词列表）。所有在同一个列表里的单词都是互为字母重排的词，也就是我们常说的“变位词”。

from collections import defaultdict

def load_words(filename='/usr/share/dict/american-english'):
    with open(filename) as f:
        for word in f:
            yield word.rstrip()

def get_anagrams(source):
    d = defaultdict(list)
    for word in source:
        key = "".join(sorted(word))
        d[key].append(word)
    return d

def print_anagrams(word_source):
    d = get_anagrams(word_source)
    for key, anagrams in d.iteritems():
        if len(anagrams) > 1:
            print(key, anagrams)

word_source = load_words()
print_anagrams(word_source)

或者：

word_source = ["car", "tree", "boy", "girl", "arc"]
print_anagrams(word_source)

Answer 3

为了对两个字符串进行这个操作，你可以这样做：

def isAnagram(str1, str2):
    str1_list = list(str1)
    str1_list.sort()
    str2_list = list(str2)
    str2_list.sort()

    return (str1_list == str2_list)

至于在列表上进行循环，这个过程非常简单明了。