使用Python,查找单词列表的字谜

Question

如果我有一个字符串列表,例如:

["car", "tree", "boy", "girl", "arc"...]

为了在该列表中找到字谜,我该怎么办？例如(car, arc).我尝试为每个字符串使用for循环,我用if它来忽略不同长度的字符串,但我无法得到正确的结果.

如何查看字符串中的每个字母并将其与列表中的其他字母按不同顺序进行比较？

我已经阅读了几个类似的问题,但答案太过先进了.我无法导入任何东西,我只能使用基本功能.

Answer 1

为了对2个字符串执行此操作,您可以执行以下操作:

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

    return (str1_list == str2_list)

至于列表上的迭代,它非常简单

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

一种解决方案是对您搜索字谜的单词进行排序(例如使用sorted),对备选方案进行排序并进行比较.

因此,如果您要在列表中搜索'rac'的字谜['car', 'girl', 'tofu', 'rca'],您的代码可能如下所示:

word = sorted('rac')
alternatives = ['car', 'girl', 'tofu', 'rca']

for alt in alternatives:
    if word == sorted(alt):
        print alt

Answer 4

由于您无法导入任何内容，因此这里有两种不同的方法，包括您要求的 for 循环。

方法 1：For 循环和内置排序函数

word_list = ["percussion", "supersonic", "car", "tree", "boy", "girl", "arc"]

# initialize a list
anagram_list = []
for word_1 in word_list: 
    for word_2 in word_list: 
        if word_1 != word_2 and (sorted(word_1)==sorted(word_2)):
            anagram_list.append(word_1)
print(anagram_list)

方法 2：字典

def freq(word):
    freq_dict = {}
    for char in word:
        freq_dict[char] = freq_dict.get(char, 0) + 1
    return freq_dict

# initialize a list
anagram_list = []
for word_1 in word_list: 
    for word_2 in word_list: 
        if word_1 != word_2 and (freq(word_1) == freq(word_2)):
            anagram_list.append(word_1)
print(anagram_list)

如果您想更详细地解释这些方法，请参阅这里的一篇文章。

Answer 5

这个问题有多种解决方案：

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))
   

   请注意，构造Counteris O(l)，而对每个单词进行排序是O(n*log(l))其中 l 是单词的长度。

2. 使用素数解字谜

   这是一个更高级的解决方案，它依赖于素数的“乘法唯一性”。您可以参考这篇 SO 帖子：Comparing anagrams using prime numbers，这里是一个 Python 实现示例。