1. 概述
在本教程中，我们将探讨如何从一个二维字母矩阵中找出所有可能的单词。这类问题在实际开发中常见于拼字游戏、路径搜索等场景。
我们会先定义问题，再通过一个具体示例进行说明，最后介绍两种不同的实现方式，并分析其时间复杂度和实现细节。
2. 问题定义
我们给定一个二维字母矩阵 M，目标是找出所有可以从该矩阵中形成的合法单词。每个单词由一条路径构成，路径的起始点是任意一个单元格，后续字母必须来自当前单元格的8个相邻单元格（上下左右+斜向），并且不能重复访问同一个单元格。
例如，以下是一个 3x3 的字母矩阵：
G O D
O O O
K I D
我们可能找到的合法单词包括：Good, God, Dog, Kid 等。
比如 Good 可以通过以下路径获得：
G (0,0) → O (1,0) → O (1,1) → D (0,2)
3. 暴力回溯法（Naive Approach）
3.1 核心思路
暴力回溯法的基本思路是尝试从每个单元格出发，生成所有可能的路径，并检查每条路径是否构成合法单词。
我们使用回溯算法（Backtracking）来遍历所有可能路径，并使用一个字典来判断当前路径是否是一个有效单词。
3.2 算法实现
algorithm NaiveApproachBacktrack(x, y, M, dictionary):
// INPUT
// M = the 2D letter matrix
// dictionary = a list of valid words
// x = current row position in matrix M
// y = current column position in matrix M
// OUTPUT
// possible_words = all possible valid words from the 2D matrix
word.append(M[x, y])
visited[x, y] <- true
for i <- 0 to length(dictionary) - 1:
if word = dictionary[i]:
possible_words.append(word)
dx <- [-1, -1, -1, 0, 0, +1, +1, +1]
dy <- [-1, 0, +1, -1, +1, -1, 0, +1]
for i <- 0 to 7:
next_x <- x + dx[i]
next_y <- y + dy[i]
if cell(next_x, next_y) in MatrixBoundary and not visited[next_x, next_y]:
NaiveApproachBacktrack(next_x, next_y, word, possible_words)
visited[x, y] <- false
word.pop(M[x, y])
3.3 时间复杂度分析
- 时间复杂度：
O(X × Y × 8^N × M)，其中：X × Y是矩阵的大小（单元格数量）8^N表示每个单元格最多有 8 个方向可走，路径长度最多为 N（单元格总数）M是字典中所有单词长度的总和
每次生成路径后，都需要遍历整个字典来判断是否是合法单词，效率较低。
4. 使用 Trie 的优化方案（Trie Approach）
4.1 核心思路
为了提升查找效率，我们可以使用 Trie 树来存储字典中的单词。这样在回溯过程中可以快速判断当前路径是否有可能构成一个合法单词，从而提前剪枝，提升性能。
4.2 构建 Trie 树
algorithm BuildTrie(dictionary):
// INPUT
// dictionary = a list of possible valid words
// OUTPUT
// the root of the trie containing all the words of the dictionary
root <- TrieNode()
for i <- 0 to length(dictionary) - 1:
root.insert(dictionary[i])
return root
4.3 回溯算法实现
algorithm TrieApproachBacktrack(x, y, trie, word, possibleWords):
// INPUT
// x = current row position in matrix M
// y = current column position in matrix M
// trie = root of the trie structure containing all valid words
// word = current word being formed
// possibleWords = set of all valid words found so far
// OUTPUT
// Adds all valid words starting from cell (x, y) in matrix M to possibleWords
if M[x, y] not in trie.children():
return
word.append(M[x, y])
trie <- trie.child(M[x, y])
visited[x, y] <- true
if trie.isWord:
possibleWords.append(word)
dx <- [-1, -1, -1, 0, 0, 1, 1, 1]
dy <- [-1, 0, 1, -1, 1, -1, 0, 1]
for i <- 0 to 7:
next_x <- x + dx[i]
next_y <- y + dy[i]
if cell(next_x, next_y) in MatrixBoundary and not visited[next_x, next_y]:
TrieApproachBacktrack(next_x, next_y, trie, word, possibleWords)
visited[x, y] <- false
word.pop(M[x, y])
trie <- trie.parent()
4.4 时间复杂度分析
- 时间复杂度：
O(X × Y × (8^N + M))，其中：X × Y是矩阵的大小8^N是路径总数（每个路径最多包含 N 个字符）M是字典中所有单词的总长度（用于构建 Trie）
相比暴力方法，Trie 优化的关键在于：
- ✅ 单词匹配时间从
O(M)降低到O(1) - ✅ 提前剪枝，避免无效路径继续搜索
5. 总结
本文介绍了从二维字母矩阵中找出所有可能单词的问题，并提供了两种实现方式：
| 方法 | 时间复杂度 | 优点 | 缺点 |
|---|---|---|---|
| 暴力回溯法 | O(X × Y × 8^N × M) |
实现简单 | 效率低，字典匹配耗时 |
| Trie 优化法 | O(X × Y × (8^N + M)) |
效率高，支持提前剪枝 | 需构建 Trie 树，空间稍大 |
✅ 推荐使用 Trie 优化方法，尤其适用于字典较大、路径较长的场景。
⚠️ 注意避免重复访问同一单元格，否则会导致死循环或错误路径。
❌ 不建议使用暴力法处理大规模矩阵或字典，效率太低。