Фон на Колесе Фортуны, для тех, кто незнаком с ним: в игре Колесо Фортуны игроки изначально видят набор пробелов, представляющих слова со скрытыми буквами. (Таким образом, игроки знают длину каждого слова, но не какие буквы содержат слова.) По ходу игры игроки угадывают буквы; если фраза содержит эту букву, все местоположения этой буквы в фразе раскрываются. Например, игра (со скрытой фразой «переполнение стека») изначально будет представлена как ????? ????????, и после угадывания буквы "o" игра отобразит ????? о ????? вл.
Для простоты предположим, что наши игры содержат только одно скрытое слово. Какую структуру данных я бы использовал для хранения всех возможных кандидатов на это слово? (Я играю с ИИ, который выбирает, какую букву угадать дальше, поэтому, чтобы сделать выбор, я хочу иметь возможность вычислять статистику, как наиболее распространенную букву из оставшихся кандидатов.) Я знаю, что мое слово содержит N букв, а затем я изучаю положения различных букв в слове, а также какие буквы слово не содержит.
Есть похожий вопрос в Хороший алгоритм и структура данных для поиска слов с пропущенными буквами? , но я думаю, что этот вопрос немного отличается тем, что у меня больше двух пробелов, и я тоже итеративное сокращение моего списка кандидатов (тогда как этот вопрос, кажется, использует только один поиск). Моя текущая идея состоит в том, чтобы просто поддерживать список слов-кандидатов, инициализированный для всех английских слов (должно быть не более 300–500 тыс. Слов), а затем (используя аналогичный подход к этому вопросу) использовать Regex для итеративного сокращения этого кандидата. перечислите, как мне кажется, больше букв, но мне любопытно, есть ли лучшая структура данных или алгоритм.