@Drembler

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

Есть матрица из букв 5х5, нужно найти все слова. Есть словарь со словами русского языка.
Следующими буквами могут быть соседние буквы и буквы по диагонали.
Нужен алгоритм по поиску слов. (или направление в какую сторону копать)
5a918a79b6fd1274433821.png
В примере слово "робко".
  • Вопрос задан
  • 189 просмотров
Решения вопроса 1
GavriKos
@GavriKos
Как одно из направлений:
Берете первую букву матрицы - отлично, проверяем есть ли в словаре такое слово. Далее от нее строим все возможные слова с двумя буквами - проверяем есть ли такое в словаре. Если по каким то путям нет слов, так же начинающихся - пути считаем невалидными.
НАпример, у нас путь на текущий момент - фхщт - в словаре нет слов, начинающихся с такого буквосочетания - дальше путь не строим.

Алгоритм далек от оптимальности, но рабочий.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
dimonchik2013
@dimonchik2013
почему ракеты не летают как птицы?
только перебор
ускорить можешь вероятностным распределением би(три-)грамм твоего словаря
Ответ написан
@syrov
пишу программы до 99 строк
это поиск в графе. т.е. либо мы используем DFS (поиск в глубину) или BFS (поиск в ширину). Еще помечать буквы которые тупиковые для позиции (например 'о' в позиции (4,3) тупиковая для первой буквы 'о' из 'робко' так как рядом нет 'б'), в общем как то исспользовать кеширование. Вот тут посмотрите:

https://www.geeksforgeeks.org/search-a-word-in-a-2...
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы