将一个字符串(任意顺序)与一个巨大数组中的字符串进行匹配

Question

def Get_Word_List(File_=[]):
    with open("Words.txt") as File: #File of 250k+ words separated via new line 
        for Line in File:
            File_.append(Line.replace("n",""))
    return File_
def Get_Input(Str=str):
    Str = raw_input("Input 7 letters: ")
    while len(Str) != 7:
        Str = raw_input("Input 7 letter: ")
    return Str.upper()
def Find_Words():
    Letters = Get_Input()
    List = Get_Word_List() #An Array of strings, all in uppercase
    for Word in List:
        pass

我试图以任何顺序匹配字符串(最大长度7)，例如"ZZAFIEA"可以给"FIZZ"或"FEZ"到一个单词或多个单词的大小为250k+的数组，我找不到办法做到这一点，我已经尝试了各种各样的，感谢任何一点帮助

Answer 1

这是一个很好的解决方案:

from collections import Counter

def counter_is_subset(x, y):
    # If subtracting y from x doesn't return an empty Counter,
    # x is NOT a subset of y.
    return not (x - y)

def find_buildable_words(words, letters):
    letters = Counter(letters)
    for word in words:
        if counter_is_subset(Counter(word), letters):
            yield word

words = ['BLAH', 'FIZZ', 'FEZ', 'FOO', 'FAZE', 'ZEE']
letters = 'ZZAFIEA'
buildable_words = find_buildable_words(words, letters)
for word in buildable_words:
    print(word)

在我的电脑上，对于250,000个单词的列表，这个运行大约需要1.2秒。

Answer 2

您可以使用itertools.ifilter，编写一个谓词来确认列表中的单词是否包含在您的字符串中，然后使用该列表上的谓词运行ifilter。

演示:

from itertools import ifilter
compare_against = "ABEFGZ"
lst = ['EFZ', 'ZIP', 'AGA', 'ABM']
def pred(word):
    for char in word:
        if char not in compare_against:
            return False
    return True
x = ifilter(pred, lst)
for y in x:
    print y

输出:

EFZ
AGA

免责声明

这个例子不能很好地处理重复的字符，意思是，根据定义，你可以决定AGA是否应该返回(字符'A'在compare_against中只出现一次)。如果您认为AGA不是一个有效的输出，则应该修改pred函数以适应该限制。