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

79. 单词搜索:题解

article 2025/3/15 20:47:17

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

初始版本（时间超越23%）

解题思路

回溯法： 每次递归尝试四个方向的相邻格子，若匹配则继续递归查找。

标记访问： 使用特殊字符 # 标记已访问的格子，防止重复使用。

终止条件： 若找到完整的单词，直接返回。

class Solution {
    public int[][] offset = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public boolean exist(char[][] board, String word) {
        List<String> res = new ArrayList<>();
        int nx = board.length;
        int ny = board[0].length;
        for (int i = 0; i < nx; i++) {
            for (int j = 0; j < ny; j++) {
                if (res.size() != 0) {
                    return true;
                }
                if (board[i][j] == word.charAt(0)) {
                    char tmp = board[i][j];
                    StringBuilder bgin = new StringBuilder();
                    bgin.append(word.charAt(0));
                    board[i][j] = '#';
                    backTrace(board, word, bgin, res, i, j);
                    board[i][j] = tmp;
                }
            }
        }
        return res.size() != 0;
    }

    public void backTrace(char[][] board, String word, StringBuilder output, List<String> res, int x, int y) {
        if (output.length() == word.length()) {
            res.add(output.toString());
            return;
        }
        int nx = board.length;
        int ny = board[0].length;
        for (int i = 0; i < 4; i++) {
            int newX = x + offset[i][0];
            int newY = y + offset[i][1];
            if (newX < 0 || newX >= nx || newY < 0 || newY >= ny) {
                continue;
            }
            char temp = word.charAt(output.length());
            if (board[newX][newY] == temp) {
                char tmp = board[newX][newY];
                output.append(temp);
                board[newX][newY] = '#';
                backTrace(board, word, output, res, newX, newY);
                output.deleteCharAt(output.length() - 1);
                board[newX][newY] = tmp;
            }
        }
    }
}

存在问题：

性能瓶颈： 使用 StringBuilder 和 List 存储路径，耗费额外空间。
未进行预剪枝： 没有在遍历前判断字母频次，导致不必要的递归。
过度递归： 没有及时返回，导致回溯路径冗长

优化解法（时间超越100）--思路来自leetcode题解区（灵茶山艾府）

class Solution {
    private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    public boolean exist(char[][] board, String word) {
        int[] cnt = new int[128];
        for (char[] row : board) {
            for (char c : row) {
                cnt[c]++;
            }
        }

        // 优化一：字符频次预剪枝
        char[] w = word.toCharArray();
        int[] wordCnt = new int[128];
        for (char c : w) {
            if (++wordCnt[c] > cnt[c]) {
                return false;
            }
        }

        // 优化二：字符顺序优化
        if (cnt[w[w.length - 1]] < cnt[w[0]]) {
            w = new StringBuilder(word).reverse().toString().toCharArray();
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (dfs(i, j, 0, board, w)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int i, int j, int k, char[][] board, char[] word) {
        if (board[i][j] != word[k]) return false;
        if (k == word.length - 1) return true;

        board[i][j] = 0;  // 标记访问
        for (int[] d : DIRS) {
            int x = i + d[0];
            int y = j + d[1];
            if (0 <= x && x < board.length && 0 <= y && y < board[x].length && dfs(x, y, k + 1, board, word)) {
                return true;
            }
        }
        board[i][j] = word[k];  // 恢复状态
        return false;
    }
}