1

给定一个二维字符矩阵，我们必须检查给定的单词是否存在于其中。例如

 s f t 
 d a h 
 r y o

我们可以在其中找到“老鼠” （自上而下、笔直、对角线或任何路径）..即使是相反的顺序。复杂性最低。

我的方法是

While traversing the 2d matrix ( a[][] ) row wise. 
If ( a[i][j] == first character of given word ) { 
    search for rest of the letters in 4 directions i.e. right, right diagonally down, down and left diagonally down. 
} else if( a[i][j] == last character of the given word ) { 
    search for remaining characters in reverse order in 4 directions i.e. left, right diagonally up, up, left diagonally up. 
}

有没有更好的方法？

4

4 回答 4

2

让我为这个问题描述一个非常酷的数据结构。

继续查找尝试。

将一个 k 长度的词插入 Trie 需要 O(k) 时间，而查找一个 k 长度的词的存在需要 O(k) 时间。

视频教程

如果您在理解或实现数据结构时遇到问题，我很乐意为您提供帮助。

于 2013-06-23T15:43:39.887 回答
0

使用简单的循环查找第一个字母或您的单词，当您找到它时，使用以下递归函数。

该函数将获取 5 个参数作为输入：您要查找的单词、您在数组中查找的str单词中字母的当前位置以及在数组中搜索字母和方向的位置。strkijd

停止条件为：

-如果k > strlen(str); return 1;

-如果arr[i][j] != str[k]; return 0;

如果上面的陈述都不是真的，你增加你的字母计数器k++；根据您的值更新您的i和并再次调用您的函数jdreturn func(str, k);

于 2013-06-23T15:51:25.553 回答
0

事实上，这里有 16 个序列：

sft
dah
ryo
sdr
fay
tho
sao
rat
tfs
had
oyr
rds
yaf
oht
oas
tar

（3 个水平 + 3 个垂直 + 2 个对角线）* 2（反转）= 16。设 n 为矩阵的大小。在您的示例中，n = 3。序列数 = (n + n + 2) * 2 = 4n + 4。

现在你需要确定一个序列是否是一个词。使用字典中的单词（在 Internet 上找到）创建一个哈希集（unordered_set在 C++ 中，在 Java 中）。HashSet您可以在 O(1) 中检查一个序列。

于 2013-06-23T15:25:47.873 回答
0

我想我会分两个阶段做到这一点：

1) 遍历数组，寻找单词中第一个字母的实例。

2) 每当您找到第一个字母的实例时，调用一个检查所有相邻单元格（例如最多 9 个）的函数，以查看它们是否是单词的第二个字母。对于找到的任何第二个字母匹配，此函数将递归调用自身并在与其相邻的单元格中查找第三个字母匹配（依此类推）。如果递归一直到达单词的最后一个字母并找到它的匹配项，则该单词存在于数组中。（请注意，如果您不允许使用两次字母，则需要将单元格标记为“已使用”，以防止算法重复使用它们。可能最简单的方法是通过-按值将已使用的单元格坐标向量放入递归函数中，

于 2013-06-23T15:37:54.893 回答