Алгоритм Вопрос по поиску всех допустимых слов в словаре

Question

Имеется словарь (просто список строк).

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

Так что, если вы получите: abpplead

Вы должны найти яблоко, бад, прокладку, свинец и т. Д.

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

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

Answer 1

Поместите словарь в три. Затем поместите буквы в массив счетчиков, индексированный по их символьным значениям, сохраняя счетчики для каждой буквы (позвольте вызывать это счетчики []). Затем выполните поиск в глубине первого порядка поиска, уменьшая значение count [letter] для каждой буквы при перемещении вниз и увеличивая его на обратном пути. Теперь, каждый раз, когда счет [буква] собирается стать отрицательным, останавливаться и перемещаться обратно вверх. Каждый раз, когда вы достигнете терминатора слова, выведите результат.

Answer 2

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

Если разрешена предварительная обработка (вы предварительно обрабатываете список один раз, а затем отвечаете на несколько запросов, достаточных для амортизации затрат на предварительную обработку), а затем для каждого слова в списке создайте «подпись», которая представляет собой массив из 26 целых чисел, подсчитывающих вхождения каждой буквы в строке (при условии, что это английский и без учета регистра - расширения очевидны). По ходу дела постройте карту от каждой подписи до списка слов, имеющих эту подпись. Эта предварительная обработка примерно равна O (N) для HashMap.

Теперь, учитывая группу из K букв, вы можете вычислить подпись группы и просмотреть каждый список слов с этой подписью на карте; повторить для всех сигнатур без равномерного распределения (O (2 ^ K) здесь верхняя граница). Так что для Z таких поисков вы платите O (N + Z * 2 ^ K) (против O (Z * N) без предварительной обработки), поэтому вы получаете (для достаточно больших чисел, чтобы оценки O () имели смысл), если N> 2 ^ К.

Answer 3

для каждого слова в словаре, проверьте, если оно из букв у вас есть только .
Чтобы проверить это, вы можете создать вспомогательную структуру, такую ​​как dict x[letter: amount], инициализировать ее количеством заданных букв и затем:

for each word 'w' in dictionary
    init x from given letters

    for each letter `ch` in word `w` 
        --x[ch]
        if x[ch] < 0
            break, do not add w to result

    result.add(w)

Answer 4

предварительно обрабатывает словарь в dawg , а затем использует один из алгоритмов обхода Догу для поиска подстрок. у меня есть некоторый базовый код ruby ​​для работы с dawg здесь ; на практике это оказалось слишком медленно, поэтому я перешел к ocaml (неизданному), но это должно дать вам представление о том, как найти анаграммы. для субанаграмм просто добавьте дополнительную проверку окончания слова, даже если ваша сумка не пуста.

Answer 5

Используйте алгоритм rete и рассматривайте проблему как проблему в области, основанной на правилах. Слова - это правила (со своими собственными буквами в качестве шаблонов правил). Для каждого набора букв вы применяете базу правил, и все совпадающие слова будут «срабатывать». Промыть и повторить. :)

[Изменить стр.]

Мотивация здесь такова: «Производительность повторов теоретически не зависит от количества правил [слов в словаре в вашем случае] в системе».

Answer 6

1.Создайте древовидную структуру для каждого слова в словаре. Ветви деревьев на каждой букве, например, первый уровень дерева - буквы a-z, следующий уровень - снова a-z, если есть какие-либо слова, использующие эту комбинацию и т. д. Листья дерева - это слова.

Затем, когда вы получите комбинацию букв, просто начните со всех вариантов выбора первой буквы, проведите дерево вниз по этой ветви, а затем выполните поиск всех вариантов выбора для второй буквы и т. Д.

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