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

Question

我正在尝试通过已知字母和字母位置（类似于填字游戏）查找单词，类似于 crosswordsolver.org 所做的

示例：

input: 
B E _ K

possible words: 
BEAK
BECK
BELK
BERK

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

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

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

提前致谢

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

用户输入一个字母一个字母地获取并存储为列表。可能有超过 1 个丢失的字母，单词长度可以是 1-10

之间的任何值

Answer 1

看看regular expression package

如：

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

会起作用。

Answer 2

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

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

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

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

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 数据结构，这样会更有效率。

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

Find Possible word by its known letters and letters position

python

crossword