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)

In the example, the word "timidly".

The following letters can be adjacent letters and the letters diagonally.

Need algorithm to find words. (or a direction in what side to dig)

In the example, the word "timidly".

asked June 7th 19 at 15:43

3 answers

answered on

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.

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.

answered on June 7th 19 at 15:47

just too much

speed up can a probability distribution bi(tri-)grams of your vocabulary

speed up can a probability distribution bi(tri-)grams of your vocabulary

answered on 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...

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

Find more questions by tags Algorithms

It's probably the only way. - Lela_Beatty commented on June 7th 19 at 15:48