leetcode hot100【LeetCode 79.单词搜索】java实现

时间：2024-11-10 18:13:09

LeetCode 79.单词搜索

题目描述

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

单词可以从网格中的任意字符开始，沿水平或垂直方向进行相邻单元格的路径查找。每个单元格只能使用一次。

示例：

输入：

board = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
]
word = "ABCCED"

输出：true

输入：

board = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
]
word = "SEE"

输出：true

输入：

board = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
]
word = "ABCB"

输出：false

Java 实现解法

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board==null || board.length==0 || board[0].length==0) return false;
        int m=board.length;
        int n=board[0].length;
        boolean[][] visited=new boolean[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,word,i,j,0,visited)){
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int i, int j, int start, boolean[][] visited){
        /**
        首先确立剪枝条件
        注意下标的特点不能够是word.length()-1  

        假设目标单词是 "ABCD"，我们从矩阵中的某个位置开始匹配。
        
        第一步：匹配第一个字符 A，start = 0。
        第二步：匹配第二个字符 B，start = 1。
        第三步：匹配第三个字符 C，start = 2。
        第四步：匹配第四个字符 D，start = 3。
        此时，start == 3，表示我们正在尝试匹配最后一个字符 D，匹配成功后，我们再调用 dfs(board, word, i, j, start + 1, visited)，
        也就是 dfs(board, word, i, j, 4, visited)，
        此时 start == 4，等于 word.length()，说明已经成功匹配了整个单词 "ABCD"。
        因此，start == word.length() 表示我们已经完全匹配了目标单词，返回 true。
        */

        if(start==word.length()){
            return true;
        }
        if(i<0 || i>=board.length || j<0 || j>=board[0].length || word.charAt(start)!=board[i][j] || visited[i][j] ){
            return false;
        }
        visited[i][j]=true;
        if( dfs(board,word,i,j+1,start+1,visited) || dfs(board,word,i,j-1,start+1,visited) || dfs(board,word,i-1,j,start+1,visited) || dfs(board,word,i+1,j,start+1,visited)){
            return true;
        }else{
            visited[i][j]=false;
            return false;
        }
    }
}

解题思路

  1. 初始化与边界检查：

    • 如果 board 为 null 或者 board 的行列数为零，直接返回 false，表示不存在单词。

  2. 遍历二维数组：

    • 从矩阵的每一个位置出发，调用 dfs 方法来进行深度优先搜索。

  3. DFS 搜索：

    • 在每个位置，首先检查当前字符是否与目标单词中的字符匹配。
    • 使用 visited 数组标记当前字符是否已经被访问，防止重复访问同一字符。
    • 搜索可以向四个方向（上下左右）扩展，递归调用 DFS。
    • 如果找到一条匹配路径，返回 true。
    • 如果没有找到匹配路径，回溯并恢复 visited 状态，继续尝试其他路径。

  4. 剪枝：

    • 如果当前字符不匹配目标单词的字符，直接返回 false，停止进一步的递归。
    • 如果索引超出了矩阵边界，也返回 false。

  5. 回溯：

    • 如果某一条路径探索完后仍然没有成功，恢复之前的 visited 状态。

复杂度分析：

  • 时间复杂度： 设 m 为矩阵的行数，n 为矩阵的列数，L 为单词的长度。

    • 最坏情况下，我们需要遍历整个矩阵的每个元素，每次从该元素开始 DFS。每次 DFS 最多会递归 L 次（单词的长度）。因此，时间复杂度为 O(m * n * 4^L)。
      • 4^L 表示每次递归有四个方向可以探索，递归的深度为 L。

  • 空间复杂度：

    • 空间复杂度主要是递归调用栈的深度和 visited 数组。递归的最大深度为单词的长度 L，所以空间复杂度为 O(L)。
    • 另外，visited 数组的空间复杂度为 O(m * n)。

相关文章