"字符矩阵中搜索词/字符串"算法的复杂性

Question

我有一项任务是从列表中搜索字母(20×20 <= MxN <= 1000×1000)单词(5 <= length <= 100)的网格.隐藏在网格中的任何单词总是呈Z字形段的形式,其长度可能只有2或3.之字形段只能是从左到右或从下到上.

所需的复杂性等于网格中字母数和列表中字母数的乘积.

对于网格:

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

和{"forward", "iterate", "phone", "satellite"} 输出的单词列表将是

3,6,iterate
6,3,satellite

我这样做了C++:
我在前缀/单词的unordered_map<string, int>where中保存了所有前缀和单词,key前缀value为1,单词为2.现在我做这样的事情(伪代码):

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

哪里:

check(string s) {
    if s is key in unsorted_map {
        if (value[s] == 2) //it's 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);
    }
}

这种实现对于网格中的随机字符和字典中的单词非常
有用但复杂度C≃O(M*N*2 ^K)> O(M*N*R)
更好的近似C≃O(M*N*(1,6) )^K)由于长度段的限制

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

最坏的情况:网格和单词中的最大网格,最大字长和相同的单个字符
如何归档所需的复杂性？只有给定的限制才有可能吗？

Answer 1

你的check()函数会做很多重复的工作。

\n\n

对于网格

\n\n

\xe2\x80\xa2aa\nab\xe2\x80\xa2\naa\xe2\x80\xa2\n

\n\n

和词'aabaa'

\n\n

有两种获取方式'aabaa'，字母后相同'b'

\n\n

（上、右、上、右）或（右、上、上、右）

\n\n

从这个特点来看，我们用一个数组a[position][n][m]来记录对于某个特定的单词是否position可以在网格中获取到其前缀和长度[m, n]

\n\n

对于前面的示例，\n遵循这样的顺序

\n\n

a[0][2][0] = true\na[1][1][0] = a[1][2][1] = true\na[2][1][1] = true\na[3][0][1] = true\na[4][0][2] = true\n

\n\n

'aabaa'可以在研磨中找到

\n\n

所以复杂度将是N*M*K*S

\n\n

S是列表中的单词数

\n