How to implement the search algorithm of words in matrix of letters?

There is a matrix of 5x5 letters, you need to find all the words. Have a dictionary with words of the Russian language.
The following letters can be adjacent letters and the letters diagonally.
Need algorithm to find words. (or a direction in what side to dig)
5a918a79b6fd1274433821.png
In the example, the word "timidly".
June 7th 19 at 15:43
3 answers
June 7th 19 at 15:45
Solution
As one of the areas:
Take the first letter of the matrix - excellent, examine to see if the dictionary has such a word. Then from it build all the possible words with two letters - check if there's one in the dictionary. If for some, no words, just starting - direction, we consider it invalid.
For example, we have a way at the moment - fhst - in dictionary has no entries starting with such letter combinations - then the path is not build.

The algorithm is far from optimal, but working.
Thank you. Also thought this way, but it seemed that too many variations will be.
It's probably the only way. - Lela_Beatty commented on June 7th 19 at 15:48
well a lot of options, Yes ( you Can chain to try as to exclude, for example. - nicklaus commented on June 7th 19 at 15:51
The way was quite good, if to optimize queries to the dictionary in php + mysql on vps average is obtained for 0.5 seconds. - Lela_Beatty commented on June 7th 19 at 15:54
can dictionary into memory to put in to be even faster. - Kaitlyn_Ledner commented on June 7th 19 at 15:57
June 7th 19 at 15:47
just too much
speed up can a probability distribution bi(tri-)grams of your vocabulary
June 7th 19 at 15:49
a search in the graph. i.e. either we use DFS (depth-first search) or BFS (breadth-first search). Else to mark letters which are dead-end positions (for example 'o' at position (4,3) of the stub for the first letter 'o' of 'shy' as there are no 'b'), in General, as it is to use caching. Look here:

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

Find more questions by tags Algorithms