C ++ - Как эффективно узнать, может ли любая строка в векторе быть собрана из набора букв

Question

Я внедряю текстовую версию Scrabble для проекта колледжа.

У меня есть вектор, содержащий около 400 тыс. Строк (мой словарь), и в какой-то момент на каждом шагу мне придется проверять , есть ли еще слово в словаре, которое можно сформировать с помощью фигуры в руке игрока. Я проверяю, осталось ли у игрока какое-либо движение ... Если нет, то игра для данного игрока окончена ...

Мое единственное решение этой проблемы - перебирать строку, одну за другой, и используя подпрограмму, я должен проверить, может ли рассматриваемая строка быть сформирована из фигур игрока. Я реализую быструю проверку, есть ли у пользователя гласные, но она все равно будет крайне неэффективной.

Текстовый файл со словарем уже упорядочен по алфавиту, поэтому вектор отсортирован.

Есть предложения?

---

Проблема была представлена ​​в комментариях ниже: Есть ли какие-либо предложения о том, как принять во внимание буквы, уже написанные на доске?

Answer 1

Без указания какого-либо конкретного кода (поскольку это домашняя работа, в конце концов), следует рассмотреть один общий подход: сопоставить от отсортированных букв в слове до реальных юридических слов.

То есть, если в вашем файле словаря есть только слова ape, gum и mug, ваша структура данных будет выглядеть следующим образом:

aep -> ape
gmu -> gum, mug

Затем вы можете просто просмотреть комбинации букв игрока и быстро определить, существует ли этот ключ на карте.

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

Answer 2

На этом сайте было много статей и вопросов по Scrabble.

Также доступно много стратегий.

Представление вашего словаря неадекватно, доступно много умных методов. Например, проверьте, что такое Trie в Википедии.

Используя это, вы можете реализовать алгоритм обратного отслеживания, чтобы быстро определить, какие слова вы можете сформировать.

{'as', 'ape', 'gum'}

Trie:

void -a-> (n) -p-> (n) -e-> (y)
              -s-> (y)
     -g-> (n) -u-> (n) -m-> (y)

Где 'n' означает, что оно не образует слово, а y означает, что оно образует.

Теперь вам просто нужно пройтись по Трие, помня о том, какие буквы доступны.

Скажите, что у вас есть {'a', 'p', 'g', 'm', 'u'}:

 1. I have a 'a' (but 'a' is not a word)
 2. I have a 'p' (but 'ap' is not a word)
 3. I don't have any 'e' so I can't go further, let's backtrack
 4. I don't have any 's' so...
 5. I have a 'g', but it's not a word
 6. I have a 'u', but 'gu' is not a word
 7. I have a 'm' and 'gum' is a word, I store it somewhere, I can't go further

Смысл в том, чтобы сохранить набор доступных букв, когда вы берете ветку -a->, вы удаляете 'a' из этого набора, а затем, когда вы берете -a-> в обратном порядке (при возврате), вы добавляете это снова в наборе.

• Эта структура намного более компактна, она фактически моделирует конечный автомат, который распознает язык вашего словаря, а не слепо сохраняет все слова
• Время выполнения также должно быть намного быстрее, так как вы никогда не будете углубляться в древовидную структуру (у вас есть только 7 доступных букв)
• Это, конечно, не то, что я бы сделал, так как не учитывает доску: p

'' буквы означают, что вы можете взять любую из доступных веток. Вам не нужно использовать пробел, если у вас есть необходимое письмо.

Answer 3

Похоже на изменение задачи о сумме подмножеств: http://en.wikipedia.org/wiki/Subset_sum_problem

Может быть, вам помогут некоторые из описанных алгоритмов.

Answer 4

Здесь уже есть несколько хороших ответов, и я думаю, что три - это, вероятно, правильный путь, но это интересная проблема, поэтому я добавлю в свои два цента ...

Наивным подходом будет генерирование всех перестановок доступных букв и всех различных подмножеств, а затем поиск каждого потенциального слова в словаре. Проблема заключается в том, что, хотя это не сложно сделать, существует на удивление большое количество потенциальных слов, и большинство из них являются недействительными.

С другой стороны, проверка словаря может быть ускорена бинарным поиском или чем-то подобным. С другой стороны, вы будете делать это так много раз, что программа остановится для длинных списков букв.

Нам определенно нужно предварительно обработать словарь, чтобы сделать его более полезным, и нам действительно нужен способ быстро исключить большинство потенциальных совпадений, даже если метод иногда дает ложные срабатывания.

Один из способов сделать это - представить, какие буквы слово использует в битовой карте. Другими словами, предварительно рассчитайте 32-битное число для каждого слова в словаре, где каждый бит устанавливается, если соответствующая буква алфавита используется в слове хотя бы один раз. Это позволит вам найти все потенциальные слова, выполнив линейное сканирование словаря и сохранив только те, которые используют только те буквы, которые у вас есть. Я подозреваю, что при некоторой сообразительности и индексации вы можете добиться большего успеха, чем линейный.

Из кандидатов, которых вы найдете, некоторым потребуется больше экземпляров письма, чем у вас имеется, поэтому это будут ложные срабатывания. Это означает, что вам необходимо выполнить окончательную проверку всех кандидатов, сгенерированных вами, чтобы исключить почти попадания. Есть много способов сделать это, но один из самых простых - просмотреть список букв и заменить первое вхождение этой буквы в потенциальном слове тире. Когда вы закончите, если у потенциального слова есть что-то кроме черточек, это провал. Более элегантным решением, хотя и не обязательно более быстрым, было бы создание массива буквенных частот и сравнение их.

Опять же, я думаю, что попытки - это, вероятно, путь, но я надеюсь, что эти идеи полезны для вас.

редактировать

Позвольте мне привести пример того, как вы могли бы добиться большего успеха, чем полный линейный поиск при первоначальном поиске: использовать основание. Держите простой индекс, который позволяет вам искать первое слово, которое начинается с данной буквы. Затем, выполняя поиск, пропустите все слова, начинающиеся с буквы, которой у вас нет. Это не гигантское ускорение, но улучшение.

Answer 5

Как насчет сохранения пар {слова из словаря, строки, состоящей из тех же букв, но в порядке возрастания (отсортировано)}

Затем отсортируйте вектор этих пар на основе второй строки и сравните, используя бинарный поиск, со строкой, состоящей из отсортированных букв из руки игроков.

Answer 6

Вы также можете сохранить строки с символами, отсортированными в ASCIIbetical порядке в std :: set, затем отсортировать буквы игрока в том же порядке и искать карту для каждой подстроки букв игрока.