当前位置：首页 > article >正文

LeetCode 79: 单词搜索 (Word Search)

article 2025/3/6 13:47:06

LeetCode 79: 单词搜索 (Word Search)

题目描述：
给定一个字母矩阵 board 和一个目标单词 word，判断该单词是否可以从矩阵中按以下规则组成：

单词中的字母必须按顺序通过相邻的单元格（上下左右四方向）。
同一个单元格内的字母不允许重复使用。

题解思路

这是一个经典的二维网格搜索问题，本质是通过深度优先搜索 (DFS) 在二维矩阵内寻找路径，同时要避免重复访问。以下是解题的关键点：

递归回溯：
DFS 是核心，一旦尝试了一个方向不满足条件，就需要回溯重新尝试其他方向。
边界条件：
- 如果超过矩阵边界，或者当前字母与目标单词不匹配，停止搜索。
- 必须检查所有方向（上、下、左、右）。
标记已访问：
- 为了避免重复访问，可以在当前路径中标记节点为已访问。
- 方法是用一个布尔型数组 visited，或者在 board 上直接修改字符（临时替换）。

解法 1：回溯 DFS

我们可以从二维网格的每一个位置出发，尝试寻找目标单词，依次搜索上下左右方向。

模板代码

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        
        // 遍历二维矩阵的每一个位置作为起点
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(board, word, i, j, 0)) { // 从每个起点开始深度优先搜索
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int i, int j, int index) {
        // 边界条件：单词匹配完成
        if (index == word.length()) return true;
        
        // 边界条件：越界或字母不匹配
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
            return false;
        }

        // 临时标记当前节点为访问过（如替换字符）
        char temp = board[i][j];
        board[i][j] = '#';

        // 递归搜索四个方向
        boolean found = dfs(board, word, i + 1, j, index + 1)
                     || dfs(board, word, i - 1, j, index + 1)
                     || dfs(board, word, i, j + 1, index + 1)
                     || dfs(board, word, i, j - 1, index + 1);

        // 回溯，将当前节点恢复为未访问状态
        board[i][j] = temp;

        return found;
    }
}

时间和空间复杂度分析

时间复杂度：O(M * N * 4^L)
- 网格大小为 M x N，每个点最多递归 4 个方向，单词长度为 L。
- 最差情况下，每个单词字符均需遍历整个搜索树。
空间复杂度：O(L)
- 递归函数的栈深度为单词长度 L，无其他额外存储。

解法 2：BFS 图搜索

相较于 DFS 的递归方式，BFS 使用队列逐层搜索，可以更好控制空间消耗。但实现较为复杂。

思路

使用队列同时存储坐标和单词匹配的位置。
对每个队列中的坐标，向四个方向扩展，直到找到完整单词或队列为空。

注意

由于 BFS 不如 DFS 直观，而且未必能直接操作矩阵，因此在竞赛中很少使用 BFS 解法。

模板代码

// BFS实现为非递归

解法 3：Trie + DFS

如果我们需要寻找多个单词，可使用 前缀树 (Trie) 优化搜索过程（见变体题目）。

常见变体及高级模板

变体 1：LeetCode 212. 单词搜索 II

问题描述：
给定一个二维字符网格和一个单词数组，找到所有可以在网格中搜索到的单词。

分析与解法：

如果对于每个单词都从网格出发执行 DFS，则时间复杂度会很高。
可使用 前缀树 (Trie) 来高效管理单词集合，降低搜索次数。

模板代码 (Trie + DFS)：

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        Trie trie = new Trie();

        // 构建前缀树
        for (String word : words) {
            trie.insert(word);
        }

        int rows = board.length, cols = board[0].length;

        // 遍历网格中每一个点，尝试匹配
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(board, trie.root, i, j, result);
            }
        }

        return result;
    }

    private void dfs(char[][] board, TrieNode node, int i, int j, List<String> result) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == '#') {
            return;
        }

        char c = board[i][j];
        if (!node.children.containsKey(c)) return;

        node = node.children.get(c);
        if (node.word != null) { // 找到一个完整单词
            result.add(node.word);
            node.word = null; // 避免重复添加
        }

        // 标记并递归
        board[i][j] = '#';
        dfs(board, node, i + 1, j, result);
        dfs(board, node, i - 1, j, result);
        dfs(board, node, i, j + 1, result);
        dfs(board, node, i, j - 1, result);
        board[i][j] = c; // 回溯
    }
}

// 前缀树节点定义
class TrieNode {
    Map<Character, TrieNode> children;
    String word;

    public TrieNode() {
        children = new HashMap<>();
        word = null;
    }
}

// 前缀树实现
class Trie {
    public TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.word = word;
    }
}