Найти возможное слово по известным буквам и положению букв

Question

Я пытаюсь найти слово по известным буквам и позициям букв (аналогично кроссворду), аналогично тому, что делает crosswordsolver.org

Пример:

input: 
B E _ K

possible words: 
BEAK
BECK
BELK
BERK

У меня есть все возможные слова (с одинаковой длиной) в списке. проблема в том, что я не могу найти правильное решение для сравнения user_input с моим списком.

Сравнение каждого индекса каждого слова в словаре с буквами слов user_input представляется решением, однако это неэффективно.

Есть ли другой способ решения этой проблемы?

заранее спасибо

РЕДАКТИРОВАТЬ: я должен добавить, что регулярное выражение не может быть использовано в качестве решения, потому что я работаю с персидскими (фарси) словами, которые используют персидский алфавит (похож на арабский)

Пользователь вводит букву за буквой и сохраняется как список. Возможно, пропущено более 1 буквы, а длина слова может быть от 1 до 10

Answer 1

Быстрый взлом

# 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, и это будет намного эффективнее.

Answer 2

Я предлагаю вам построить дерево с вашим списком слов.

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

Поиск будет быстрым и потребление памяти будет низким.

Если вы не хотите начинать с нуля, вы можете использовать модуль anytree.

Answer 3

Посмотрите на пакет регулярных выражений

Что-то как:

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

должно сработать.