Как реализовать алгоритм поиска слов в матрице из букв?

Question

[Drembler]

Есть матрица из букв 5х5, нужно найти все слова. Есть словарь со словами русского языка.
Следующими буквами могут быть соседние буквы и буквы по диагонали.
Нужен алгоритм по поиску слов. (или направление в какую сторону копать)

В примере слово "робко".

Answer 1

[GavriKos]

Как одно из направлений:
Берете первую букву матрицы - отлично, проверяем есть ли в словаре такое слово. Далее от нее строим все возможные слова с двумя буквами - проверяем есть ли такое в словаре. Если по каким то путям нет слов, так же начинающихся - пути считаем невалидными.
НАпример, у нас путь на текущий момент - фхщт - в словаре нет слов, начинающихся с такого буквосочетания - дальше путь не строим.

Алгоритм далек от оптимальности, но рабочий.

Comments

[Drembler]

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

[GavriKos]

Drembler, ну, вариантов немало, да ( Можно цепочками пробовать как то исключать, например.

[Drembler]

GavriKos, Способ оказался довольно неплохим, если оптимизировать запросы к словарю, то в php + mysql на средненьком vps получается за 0,5 сек.

[Владимир Олохтонов]

Drembler, можно словарь в память положить в виде множества, будет ещё быстрее.

Answer 2

[Андрюха]

это поиск в графе. т.е. либо мы используем DFS (поиск в глубину) или BFS (поиск в ширину). Еще помечать буквы которые тупиковые для позиции (например 'о' в позиции (4,3) тупиковая для первой буквы 'о' из 'робко' так как рядом нет 'б'), в общем как то исспользовать кеширование. Вот тут посмотрите:

https://www.geeksforgeeks.org/search-a-word-in-a-2...

Answer 3

[Dimonchik]

только перебор
ускорить можешь вероятностным распределением би(три-)грамм твоего словаря