我有一个任务,需要在字母网格中(
要求的复杂度等于网格中字母数和列表中字母数的乘积。
对于该网格:
我用C++实现了以下代码:
我把所有的前缀和单词保存在一个unordered_map中,其中key是前缀/单词,value为1表示前缀,为2表示单词。现在我执行类似于以下的操作(伪代码):
这个实现对于网格中的随机字符和来自字典的单词效果很好,但是复杂度为C ≃ O(M * N * 2^K) > O(M * N * R)。更好的近似值是 C ≃ O(M * N * (1,6)^K),因为长度段的限制。
最坏情况:最大网格,最大单词长度以及网格和单词中相同的单个字符。 我如何实现所需的复杂性?这仅在给定的限制条件下可能吗?
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
最坏情况:最大网格,最大单词长度以及网格和单词中相同的单个字符。 我如何实现所需的复杂性?这仅在给定的限制条件下可能吗?
(5 <= K <= 100)
。对于 {"forward", "iterate", "phone", "satellite"},K = strlen("satellite") = 9。 - Jorj