2

如果一个单词存在于随机字母 (AZ) 的 4x4 网格中，您将如何进行搜索。有人能引导我找到解决这个问题的有效方法的正确方向吗？

以下是条件：

  • 单词由相邻的字母组成
  • 单词可以水平，垂直或对角向左，向右或上下形成
  • 在一个单词中不能多次使用字母单元格。

谢谢你们的帮助！

4

3 回答 3

2

您可以将此视为图形问题。将网格转换为图形，其中每个顶点代表网格中的一个单元格，顶点之间的边代表这些单元格之间的有效移动。

从那里，您可以使用以下递归算法来确定是否可以在图 G 中找到单词 S：

查找字（G，S）：
1. 将 C 设置为 S 的第一个字母。
2. 将 S' 设置为 S，去掉第一个字母。
3. 对于 G 中的所有顶点 V：
  3.1。如果 V 中的字母不是 C，则继续下一个顶点。
  3.2. 如果 CheckPaths(G, S', V, {}) 返回 true，则返回 true。
4. 返回假。

检查路径（G、S、V、已访问）：
1. 如果 S 为空，则返回 true。
2. 将 C 设置为 S 的第一个字母。
3. 将 S' 设置为 S，去掉第一个字母。
4. 将 Visited' 设置为 Visited ∪ {V}。
5. 对于连接到 V 的所有单元 V'：
  5.1。如果 V' ∈ Visited，继续下一个顶点。
  5.2. 如果 V' 中的字母不是 C，则继续下一个顶点。
  5.3. 如果 CheckPaths(G, S', V', Visited') 返回 true，则返回 true。
6.返回假。

实际的实现可能会有点不同（例如，最好不要复制已访问的副本，而是在确定路径失败后通过删除顶点来共享单个集合），但这是关于如何去做吧。

于 2012-01-27T23:46:53.450 回答
1

如果您只是在 4X4 网格上工作，它应该非常简单。扫描单词的第一个字母，并在各个方向搜索该单词是否可以从网格中完成。

如果网格非常大和/或您正在执行大量搜索，您可能需要先预处理网格。例如。对于每两个字符（我们称它们为 k-gram，因为通常您想要跟踪 k 个字符），您可以保留它们所在位置的列表。搜索时，首先查找该单词的 k-gram 位置。

于 2012-01-27T23:28:34.107 回答
1

我将从一个既有字母又有空格的网格表示开始。

我会编写一个例程，将像这样的网格和一个起始字母作为参数，并返回一个可能单词的列表。

对于这样的网格，我会编写一个迭代器，它返回与给定字母相邻的每个字母。它会识别空格并且不会返回它们。

我会编写一个例程，将一个字母和我的网格从网格中删除，并且对于每个相邻的字母，用新的网格和新的字母调用它自己。

如果你真的想搜索一个单词，你可以将它传递到这些例程中，这样一旦你有一个不匹配的结果就可以失败。

否则，您可以使用它来生成完整的单词列表。

于 2012-01-27T23:43:30.967 回答