Dx's Tech Notes

6.单词搜索

3 min read

  • 2.13
    • 主函数 for 里是 if，只要找到一个就返回 true
    • 需要 word 来取当前位置的 char，需要 n 来做游标看是否 n 等于字符长度
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,i,j,word,0)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,int i,int j,String word,int k){
        if(k==word.length()) return true;
        if(i<0||i>=board.length||j<0||j>=board[0].length||word.charAt(k)!=board[i][j])return false;
        char temp = board[i][j];
        board[i][j]='#';
        boolean res = 
        dfs(board,i+1,j,word,k+1)||
        dfs(board,i,j+1,word,k+1)||
        dfs(board,i-1,j,word,k+1)||
        dfs(board,i,j-1,word,k+1);
        board[i][j]=temp;
        return res;
    }
}
  • 2.3
    • 是回溯的思路，但是表现是 dfs 遍历每个节点（上下左右遍历）
      • 难点：坐标 ij 参数，k 作为 word 的位置参数
      • 先判断是否越界，再判断是否等于，再判断是不不是满了（或者先判断是不是满了，如果没满在判断越界和是否相等）
      • 之后回溯先标记，在回溯（上下左右 dfs），再去掉标记，范围 boolean
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,i,j,word,0)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,int i, int j,String word,int k){
        if(k==word.length()) return true;
 
        if(i<0||i>board.length-1||j<0||j>board[0].length-1) return false;
        if(word.charAt(k)!= board[i][j]) return false;
        char temp = board[i][j];
        board[i][j]='#';
        boolean found = 
        dfs(board,i+1,j,word,k+1)||
        dfs(board,i,j+1,word,k+1)||
        dfs(board,i-1,j,word,k+1)||
        dfs(board,i,j-1,word,k+1);
        board[i][j] = temp;
        return found;
    }
}
  • 11.30
    • 在dfs中,先判等不等于或是否越界,在判断长度是否相等,看跳出条件
    • 之后就是回溯思路,先存路径(做标记),在判断(四个方向),之后回溯(消除标记),返回回溯结果
    • 在主函数中每个棋格进行dfs操作
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,word,i,j,0)) return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,String word,int i,int j,int k){
        if(i<0||i>=board.length||j<0||j>=board[0].length) return false;
        if(board[i][j] != word.charAt(k)) return false;
        if(k==word.length()-1) return true;
        char temp = board[i][j];
        board[i][j]='#';
        boolean found = dfs(board,word,i+1,j,k+1) ||
                        dfs(board,word,i,j+1,k+1) ||
                        dfs(board,word,i-1,j,k+1) ||
                        dfs(board,word,i,j-1,k+1);
        board[i][j] = temp;
        return found;
    }
}

整体框架

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (dfs(board, word, i, j, 0)) return true;
    }
}
return false;

🚀 DFS 搜索逻辑（重点）

假设我们在 (i, j) 位置，当前要匹配 word[k]：

  1. 终止条件：
    • k == word.length() → 匹配完成 ✅
    • 越界 / 已访问 / 字符不匹配 → 剪枝 ❌
  2. 匹配当前字符后，向上下左右四个方向继续搜索： dfs(i+1, j, k+1) dfs(i-1, j, k+1) dfs(i, j+1, k+1) dfs(i, j-1, k+1)
  3. 访问状态处理（回溯）：
    • 标记当前格子“已访问”；
    • 递归结束后恢复原样。

Graph View

Backlinks