深入解析单词搜索（Word Search）算法与应用

单词搜索（Word Search）是一类在给定字符网格中寻找目标单词的问题，常见于益智游戏和算法面试。本文将从最朴素的解法出发，逐步引入高效的数据结构优化，并探讨其现实应用。

1. 问题定义

给定一个 M × N 的二维字符网格和一个字符串列表作为词典，需要判断网格中是否存在能通过上下左右相邻单元格（不重复使用）组成词典中单词的路径。例如，在以下网格中查找单词“CAT”：

['C','A','T']
['R','E','S']
['P','L','E']

路径可以是 (0,0)->(0,1)->(0,2)。

2. 经典解法：回溯

最直接的方法是深度优先搜索（DFS）加回溯。对每个单元格，若首字母匹配则开始递归，沿四个方向探索，同时标记已访问单元格避免重复。复杂度为 O(M × N × 4^L)，其中 L 为单词最大长度。若不优化，对于大网格和长词典效率极低。

3. 优化：前缀树（Trie）

当词典包含大量单词时，可以先将所有单词构建成一颗 Trie 树。搜索时仅在 Trie 中存在的路径上继续，大幅剪枝。复杂度可降至 O(M × N × 4^(L_avg))，实际速度显著提升。

3.1 构建 Trie

例如词典包含 ["cat", "car", "rat"]，Trie 结构如下：

根节点
├── c → a → t (单词结束)
│         └── r (单词结束)
└── r → a → t (单词结束)

搜索时，从网格每个单元格开始，如果当前前缀存在于 Trie 中则继续，否则回溯。

4. 高级优化

• 剪枝：若剩余字符不足，提前终止。
• 顺序优化：按单词长度降序搜索，长单词更易找到。
• 位掩码：用整数标记访问状态，减少空间开销。

5. 应用场景

单词搜索不仅用于游戏（如 Boggle、Word Hunt），还在自然语言处理中用于拼写检查和关键词提取。例如，可在 OCR 识别后的文本网格中查找特定术语。

6. 代码示例（Python）

def findWords(board, words):
    # 构建Trie
    trie = {}
    for w in words:
        node = trie
        for ch in w:
            node = node.setdefault(ch, {})
        node['#'] = True  # 标记单词结束

    def dfs(i, j, parent, path):
        ch = board[i][j]
        node = parent.get(ch)
        if not node:
            return
        if '#' in node:
            result.append(path)
            del node['#']  # 避免重复
        board[i][j] = '#'  # 标记访问
        for x, y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
            if 0 ≤ x < m and 0 ≤ y < n and board[x][y] != '#':
                dfs(x, y, node, path + board[x][y])
        board[i][j] = ch

    m, n = len(board), len(board[0])
    result = []
    for i in range(m):
        for j in range(n):
            dfs(i, j, trie, board[i][j])
    return result

7. 总结

单词搜索问题融合了搜索、剪枝与数据结构设计，是算法学习的典型范例。通过 Trie 优化，可将指数级复杂度控制在可接受范围。实际开发中，还可结合多线程、分布式搜索进一步提升性能。