python - 通过已知字母和字母位置查找可能的单词

Question

我试图通过其已知字母和字母位置（类似于填字游戏）来查找一个单词，类似于 crosswordsolver.org 所做的

例子 ：

input: 
B E _ K

possible words: 
BEAK
BECK
BELK
BERK

我在一个列表中有所有可能的单词（长度相同）。问题是，我找不到合适的解决方案来将 user_input 与我的列表进行比较。

将字典中每个单词的每个索引与 user_input 单词字母进行比较似乎是一种解决方案，但它根本没有效率。

有没有其他方法可以解决这个问题？

先感谢您

编辑：我应该补充一点，正则表达式不能用作解决方案，因为我正在使用波斯语（波斯语）单词，它使用波斯字母（类似于阿拉伯语）

用户输入一个字母一个字母并存储为列表。可能有超过 1 个缺失的字母，单词长度可以是 1-10 之间的任何值

Answer 1

我建议你用你的单词列表构建一棵树。

*-+-A
  |
  +-B-+-A
  |   |
      +-B
      |
      +-C
      |
      +-C
      |
      +-E-+-A-+
      |   |   |
              .
              .
              |
              +-K-x ("BEAK")

搜索速度快，内存消耗低。

如果您不想从头开始，可以使用模块 anytree。

Answer 2

看看正则表达式包

比如：

import re
pattern = re.compile('BE.K')
possible_words = [word for word in all_words if re.match(pattern, word)]

会工作。

Answer 3

快速破解

# Save pattern as (char, position) where position starts at 0
pattern = [("B", 0), ("E", 1), ("K", 3)] 

dictionary = ["BEAK", "BECK", "BELK", "BERK"]

def match(word, pattern):
    if len(pattern) > len(word):
        return false

    return all(word[pos] == c for (c, pos) in pattern):

def list_matches(pattern, dictionary):
    for word in dictionary:
        if match(word, pattern):
            print(word)

list_matches(pattern, dictionary)

您可以使用Trie数据结构，这样效率会更高。