Complexity of "Search Words / Strings in the Char Matrix" Algorithm

Question

I have a task of searching in a grid of letters ( 20×20 <= MxN <= 1000×1000 ) words ( 5 <= length <= 100 ) from a list. Any word hidden in the grid is always presented in the form of zigzag segments, the length of which can be only 2 or 3. Zigzag segments can be only from left to right or from bottom to top.

The required complexity is the product of the number of letters in the grid and the number of letters in the list.

For the grid:

 •••••••••••••••••••• ••••••••ate•••••x••• •••••••er•••••••e••• ••••••it••••••••v••• ••••ell••••••a••f••• •••at••••e••••••rbg• •••s•••••••ga••••••• 

and a list of words {"forward", "iterate", "phone", "satellite"} output will be

 3,6,iterate 6,3,satellite 

I did this in C++ :
I saved all the prefixes and words in unordered_map<string, int> , where key is the prefix / word and value is 1 for the prefix and 2 for the word. Now I am doing something like this (pseudocode):

 for (char c in grid) check(c + ""); } 

Where:

 check(string s) { if s is key in unsorted_map { if (value[s] == 2) //it a word print s; //and position if (not up 3 time consecutive) //limit the segments <= 3 check(s + next_up_char_from_grid); if (not right 3 time consecutive) check(s + next_right_char_from_grid); } } 

This implementation works fine for random characters in a grid and words from a dictionary, but
complexity C ≃ O (M * N * 2 ^K )> O (M * N * R) <Best approximation C ≃ O (M * N * (1,6) ^K ) due to length segment restrictions

 M * N = number of chars in grid K = the maximum length of any word from list (5 <= K <= 100) R = number of chars in list of words 

Worst case: max grid, max word length and one single char in grid and word
How can I archive the required complexity? Is it possible only with the given restrictions?

Answer 1

Your check() function will do many repeat operations.

For mesh

 •aa ab• aa• 

and the word 'aabaa'

There are two ways to get 'aabaa' , which are the same after the letter 'b'

(top, right, top, right) or (right, top, top, right)

From this attribute, we use the array a[position][n][m] to record whether its prefix with length position can be obtained for a specific word in the grid [m, n]

In the previous example, follow this sequence

 a[0][2][0] = true a[1][1][0] = a[1][2][1] = true a[2][1][1] = true a[3][0][1] = true a[4][0][2] = true 

'aabaa' can be found in grind

So the complexity will be N*M*K*S

S - number of words in the list