c++ - Complexity of the "Search words/strings in Matrix of Char" Algorithm -

i have task search in grid of letters (20×20 <= mxn <= 1000×1000) words (5 <= length <= 100) list. word hidden in grid in form of zig-zag segments length may 2 or 3. zigzag segments can left right or bottom top.

the complexity required equal product of number of letters in grid , number of letters list.

for grid:

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

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

3,6,iterate 6,3,satellite 

i did in c++:
saved prefixes , words in unordered_map<string, int> key prefix/word , value 1 prefix , 2 word. (pseudocode):

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

where:

check(string s) {     if s key in unsorted_map {         if (value[s] == 2) //it's word             print s; //and position         if (not 3 time consecutive) //limit 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 great random chars in grid , words dictionary
complexity c ≃ o(m * n * 2^k) > o(m * n * r)
better approximation c ≃ o(m * n * (1,6)^k) because of restrictions of length segments

m * n = number of chars in grid k = maximum length of word list (5 <= k <= 100) r = number of chars in list of words 

worst case: max grid, max word length , same single char in grid , word
how can archive required complexity? possible given restrictions?

your check() function many repetition work.

for grid

•aa ab• aa• 

and word 'aabaa'

there 2 ways 'aabaa' same after letter 'b'

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

from trait, use array a[position][n][m] record whether specific word prefix length position can got @ grid [m, n]

for previous example, follow such 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 found in grind

so complexity n*m*k*s

s number of words in list