C ++ Boggle Solver: Поиск префиксов в наборе

Question

Это для домашнего задания, поэтому я не хочу точного кода, но буду признателен за любые идеи, которые могут помочь мне указать верное направление.

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

Мне необходимо хранить словарь либо в наборе, либо в отсортированном списке.,Я пытался реализовать это с помощью набора.Чтобы программа работала быстрее и не следовала тупиковым путям, мне нужно проверить и посмотреть, существует ли текущая последовательность символов в качестве префикса к чему-либо в наборе (словаре).

Я нашелэта операция set.find () возвращает true, только если строка является точным соответствием.В лабораторных требованиях профессор упоминал, что:

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

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

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

Я также думал об использовании strncmp () для сравнения текущей последовательности со словом из набора словарей,но опять же, я не знаю, как именно это будет функционировать в этой ситуации, если вообще будет.

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

Спасибо

Answer 1

Как @Raymond Hettinger упоминает в своем ответе, trie было бы здесь чрезвычайно полезно. Однако, если вам неудобно писать три или вы предпочитаете использовать готовые компоненты, вы можете использовать симпатичное свойство того, как слова упорядочены в алфавитном порядке, чтобы за O (log n) проверить, существует ли данный префикс. Идея заключается в следующем - предположим, например, что вы проверяете префикс «thr». Если вы заметите, каждое слово, начинающееся с префикса «thr», должно быть зажато между строками «thr» и «ths». Например, thr & le; через

Поскольку вы используете C ++, вы можете сделать это с помощью алгоритма std::vector и std::lower_bound. Вы также можете выбросить все слова в std::set и использовать set версию lower_bound. Например:

std::set<std::string> dictionary;
std::string prefix = /* ... */

/* Get the next prefix. */
std::string nextPrefix = prefix;
nextPrefix[nextPrefix.length() - 1]++;

/* Check whether there is something with the prefix. */
if (dictionary.lower_bound(prefix) != dictionary.lower_bound(nextPrefix)) {
    /* ... something has that prefix ... */
} else {
    /* ... no word has that prefix ... */
}

Тем не менее, дерево, вероятно, здесь лучше. Если вам интересно, есть другая структура данных, называемая DAWG (направленный ациклический граф слов) , которая похожа на три, но использует существенно меньше памяти; на вводных курсах CS в Стэнфорде (где Boggle - это задание) студентам фактически предоставляется DAWG, содержащая все слова на языке. Существует также другая структура данных, называемая троичным деревом поиска , которая находится где-то между бинарным деревом поиска и деревом, которые могут быть полезны здесь, если вы хотите посмотреть на него.

Надеюсь, это поможет!

Answer 2

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

Если вы ограничены наборами и словарями, я бы выбрал словарь, который отображает префиксы в массив возможных совпадений:

asp -> aspberger aspire
bal -> balloon balance bale baleen ...