“在字符矩阵中搜索单词/字符串”算法的复杂性

Question

我有一个任务，需要在字母网格中（20×20 ≤ MxN ≤ 1000×1000）搜索列表中的单词（5 ≤ length ≤ 100）。任何隐藏在网格中的单词都以锯齿形线段的形式出现，其长度只能为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中，其中key是前缀/单词，value为1表示前缀，为2表示单词。现在我执行类似于以下的操作（伪代码）：

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

where:

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

最坏情况：最大网格，最大单词长度以及网格和单词中相同的单个字符。 我如何实现所需的复杂性？这仅在给定的限制条件下可能吗？

- Jorj

---

你的复杂度中的K是什么？ - Fabinout

K = 列表中任何单词的最大长度 (5 <= K <= 100)。对于 {"forward", "iterate", "phone", "satellite"}，K = strlen("satellite") = 9。 - Jorj

我猜你需要一个单词搜索谜题的算法？ - mijail

Answer 1

你的 check() 函数将会执行很多重复的工作。

对于网格。

•aa
ab•
aa•

和单词'aabaa'

有两种方式可以得到在字母'b'之后仍然相同的'aabaa'

(上，右，上，右)或(右，上，上，右)

基于这个特性，我们使用一个数组a[position][n][m]来记录对于一个特定的单词，它的长度为position的前缀是否可以在网格[m, n]中获得

对于前面的例子，按照这样的顺序进行

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'。

所以复杂度将为N*M*K*S。

S是列表中的单词数量。

- LTzycLT