我的任务是从列表中搜索字母 ( 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<string, int>
中其中 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 * 2K) > O(M * N * R) < br/> 由于长度段的限制,更好的近似 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
最坏情况:最大网格、最大字长以及网格和单词中相同的单个字符
如何归档所需的复杂性?只有在给定的限制条件下才有可能吗?
最佳答案
您的 check()
函数将执行许多重复工作。
对于网格
•aa
ab•
aa•
和单词'aabaa'
有两种获取'aabaa'
的方法,在字母'b'
之后是一样的
(上,右,上,右)或(右,上,上,右)
从这个特征出发,我们使用一个数组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'
可以在grind中找到
所以复杂度将是 N*M*K*S
S
是列表中的单词数
关于c++ - "Search words/strings in Matrix of Char"算法的复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31479226/