Java 中的 Boggle 搜索问题

Boggle 游戏是一款流行的单词搜索益智游戏，玩家尝试在字母网格中查找隐藏的单词。目标是根据预定义的规则，通过相邻的字母找到路径来组成单词。在编程术语中，解决 Boggle 游戏涉及从字典中高效搜索所有可以在给定网格中构建的有效单词。

注意：单词必须至少包含三个字母。

因此，在上面的 Boggle 板或网格中，我们可以看到以下单词。

EAR (索引 2, 3 和 4)

EARN (索引 2, 3, 4 和 7)

RUN (索引 5, 6, 7)

WINE (索引 11, 12, 8, 2)

WIN (索引 11, 12, 8)

MAT (索引 10,14, 15)

MATE (索引 10, 15, 15, 16)

示例 1

输入

输出

 
["ABCCED", "SEE"]   

解决 Boggle 搜索问题

Boggle 搜索问题可以通过各种方法解决，例如，暴力破解法、深度优先搜索、优化方法、Trie 方法和回溯法等。

我们给出了一个 4x4 的字母矩阵和一个字典，找出矩阵中的所有有效单词。以下是必须遵循的条件。

1. 如果一个字母被使用，它在同一次单词搜索中不应再次使用。
2. 单词路径可以是任何方向。
3. 必须存在一个字母路径来组成单词（换句话说，单词中的所有字母必须彼此相邻）。

深度优先遍历

深度优先遍历涉及在回溯之前尽可能深入地探索树或图结构的每个分支。它优先考虑深度而非广度，通常通过递归实现，因此非常适合路径查找或游戏/算法（如 Boggle 搜索问题）中的穷举搜索等任务。

在这种方法中，我们将每个字符视为起始字符，并查找以该字符开头的所有单词。可以使用深度优先遍历找到从某个字符开始的所有单词。我们从每个单元格开始进行深度优先遍历。我们跟踪已访问的单元格，以确保一个单元格在一个单词中只被考虑一次。

文件名：BoggleDFS.java

输出

 
Following words of dictionary are present IN Boggle Grid:
EAR
EARN
RUN
EAR
EARN
MAT
MATE
WIN
WINE
WINE   

请注意，上面的解决方案可能会多次打印同一个单词。例如，如果我们向字典中添加“WINE”、“EARN”，它们会被多次打印。为了避免这种情况，我们可以使用哈希表来跟踪所有已打印的单词。

现在是时间复杂度，由于我们对数组中的每个位置都进行深度优先遍历，因此 n*m（一次 DFS 的时间）= n*m（|V| + |E|），其中 |V| 是总节点数，|E| 是总边数，它们都等于 n*m。

时间复杂度： O(N² *M²)

辅助空间： O(N*M)

优化方法

步骤 1： 初始化 Boggle 板（board）、字典（dictionary）、用于跟踪已访问单元格的 visited 数组，以及用于存储在板上找到的有效单词的 foundWords() 列表。

步骤 2： 遍历字典中的每个单词。使用 canFormWord() 方法检查单词是否可以在板上形成。如果可以形成，则将单词添加到 foundWords()。

步骤 3： 遍历板上的每个单元格。从每个单元格调用 dfs() 方法，以检查是否可以从该单元格开始形成单词。

步骤 4： 如果索引等于单词的长度，则表示整个单词已匹配，因此返回 true。检查是否超出边界、单元格是否已被访问或字符是否不匹配，并相应地返回 false。

• 将当前单元格 (board[x][y]) 标记为已访问 (visited[x][y] = true)。
• 递归地探索所有 8 个方向上的相邻单元格（x-1, y, x+1, y, x, y-1, x, y+1 等），继续匹配单词的后续字符。
• 如果找到有效路径，dfs() 函数将返回 true。

步骤 5： 在返回之前，通过将当前单元格标记为未访问 (visited[x][y] = false) 来进行回溯。

让我们在 Java 程序中实现上述算法。

文件名：BoggleSolver.java

输出

 
Words found:
abc
beh
cfi   

时间复杂度： O(N × R × C × 8^W)，其中 N 是字典中的单词数，R 是行数，C 是板的列数，W 是单词的平均长度。

辅助空间复杂度： O(R × C + N + W)，其中 R × C 用于 visited 数组，N 用于存储找到的单词，W 用于 DFS 遍历期间的递归堆栈深度。

递归 + 二分查找方法

在此方法中，我们递归地（使用回溯）遍历板并生成所有可能的单词。对于长度为三或更多个字母的每个单词，我们检查它是否存在于字典中。如果存在，则匹配成功。以下是算法步骤。

1. 将字典读入内存中的容器。
2. 对字典进行排序。
3. 使用回溯在板上搜索单词。
4. 如果找到一个单词且其长度为 3 个或更多字母，则对字典进行二分查找以确定该单词是否存在。
5. 如果上一步的搜索成功，则打印该字母。
6. 只要板上还有更多单词可构造，就继续执行步骤 3-5。

复杂度

在此解决方案中，我们在字典搜索方面做得很好。使用二分查找，我们可以快速确定一个单词是否存在于字典中。但真正的瓶颈在于在板上搜索单词。对于 N x N 的板，搜索空间为 O((N*N)!)。

剪枝递归 + 前缀树（也称为 Trie）方法

与前一种方法相比，我们的主要担忧是板上巨大的搜索空间。幸运的是，使用前缀树或 Trie 数据结构，我们可以显著减少搜索空间。这种改进背后的原理是，如果一个单词“abc”在字典中的任何单词中都不是前缀，那么在我们遇到板上的“abc”之后，就没有理由继续搜索单词了。它实际上大大缩短了运行时间。以下是算法步骤。

1. 从字典文件中读取一个单词。
2. 将其插入内存中的前缀树数据结构。
3. 重复步骤 1-2，直到字典中的所有单词都已插入前缀树。
4. 使用回溯在板上搜索单词。
5. 如果找到一个单词且其长度为 3 个或更多字母，则在前缀树中搜索该单词。
6. 如果上一步的搜索*不*成功，则从回溯阶段的该分支返回。（在这种情况下，没有继续在此分支中搜索的意义，因为前缀树表明字典中不存在）。
7. 如果在步骤 5 中搜索成功，则通过沿着此回溯分支构建更多单词来继续搜索，并在前缀树中的叶节点处停止。（此时没有更多可搜索的内容）。
8. 只要回溯中有更多单词可供搜索，就重复步骤 4-7。

复杂度

此方法对第一种方法进行了显著改进。使用字典单词构建前缀树的复杂度为 O(W * L)，其中 W 是字典中的单词数，L 是字典中最长单词的长度。

搜索板的复杂度与字典的复杂度相同，因为我们实际上并没有搜索不在字典中的单词。但实际上，这需要更多的工作，因为我们仍然需要沿着板回溯以构建新单词，直到我们可以查阅字典前缀树以了解其是否存在。

无搜索空间 + 动态规划方法

上面提到的第二种方法在板尺寸为 5 时效果很好。然而，当板尺寸为 6 时，即使是它也需要很长时间才能完成！

这让我思考——“糟糕，这个搜索空间仍然太大了，无法搜索！我能完全摆脱它吗？”然后我脑海中闪过一个想法：与其在无限的单词海洋中随机构造一个接一个的单词，为什么不直接从字典中取一个单词，然后以某种神奇的方式检查它是否可以在板上构造出来呢？

事实证明，我们可以使用一种巧妙的动态规划技术来快速检查一个单词（在本例中为字典中的单词）是否可以从板上构造出来！

以下是动态规划思想的核心要点。

要找到一个长度为 k 的单词（结束位置）在板的 [i, j] 位置，该单词的第 k-1 个字母必须位于 [i, j] 的相邻单元格之一中。

基本情况是 k = 1。

长度为 1 的字母将在板的 [i, j] 单元格中找到（结束位置），前提是单词中的字母与板的 [i, j] 位置中的字母匹配。

一旦我们的动态规划表用基本情况填充，我们就可以为任何长度为 k（k > 1）的单词在此基础上进行构建。

以下是此代码的示例。