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

79. 单词搜索:题解

给定一个 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;
            }
        }
    }
}

存在问题:

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

优化解法(时间超越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;
    }
}
第一个优化:字符频次预检查

先统计棋盘中每个字符的数量,再统计单词中每个字符的数量。
如果单词中的某个字符次数多于棋盘中该字符次数,直接返回 false,避免无意义搜索。

第二个优化:优先搜索稀有字符

如果单词的第一个字符最后一个字符在棋盘中出现次数更多,就把单词反转,从稀有字符开始搜索。
这样可以更快地发现不匹配,减少搜索次数。

稀有宝石难找,先找稀有的


http://www.kler.cn/a/586008.html

相关文章:

  • sap关账+策略模式(避免大量if elseif)
  • SpringBoot注解驱动CRUD工具:spring-avue-plus
  • BOE(京东方)携手微博举办“微博影像年”年度影像大展 创新科技赋能专业影像惊艳呈现
  • 芯谷D8563TS:低功耗CMOS实时时钟/日历电路的优选方案
  • CentOS-7安装Docker(更新时间:2025-03-12)
  • markdown 转 word 工具 ‌Pandoc‌
  • 谷歌手机LEA流程
  • Vue 中的 transition 组件如何处理动画效果?
  • 世界坐标到UV纹理坐标的映射
  • PinnDE:基于物理信息神经网络的微分方程求解库
  • RabbitMQ入门:从安装到高级消息模式
  • axios配置全局接口超时时间
  • 某乎x-zse-96加密算法分析与还原
  • Leetcode3340:检查平衡字符串
  • 【漫话机器学习系列】132.概率质量函数(Probability Mass Function, PMF)
  • 软件性能测试与功能测试联系和区别
  • 开源:LMDB 操作工具:lmcmd
  • 笔试刷题专题(一)
  • 《MySQL数据库从零搭建到高效管理|表的增删改查(基础)》
  • STM32与HAL库开发实战:深入探索ESP8266的多种工作模式