【LeetCode】79. 单词搜索(回溯的另一种框架)（剑指12）

题目链接

79. 单词搜索

题目描述

解题思路

又是一题经典的回溯法，但是本题回溯法的框架和之前的回溯题目不一样，可以进行对比分析。

AC代码

class Solution {

    int dir[][] = {{0,1},{0,-1},{-1,0},{1,0}};

    boolean dfs(char[][] board,int[][] vis,int x,int y,int num,String word){
        if(board[x][y] != word.charAt(num)) return false;
        if(num == word.length()-1) return true;     
        for(int i = 0; i < 4; i++){
            vis[x][y] = 1;
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if(xx>=0&&xx<board.length&&yy>=0&&yy<board[0].length&&vis[xx][yy]==0){ 
                //将dfs语句放入if语句判断，可以减少回溯的复杂度，避免程序超时，一开始就是直接一条dfs语句，用例应该都能过，但是时间超时了，最终只过了百分之98个案例
                if(dfs(board,vis,xx,yy,num+1,word)) return true;
            }
            vis[x][y] = 0;
        }
        return false;
    }

    public boolean exist(char[][] board, String word) {
        int x_len = board.length;
        int y_len = board[0].length;
        int[][] vis = new int[x_len][y_len];
        for(int i = 0; i < x_len; i++){
            for(int j = 0; j < y_len; j++){
       			//返回值只有true和false的小技巧！！
                if(dfs(board,vis,i,j,0,word)){
                    return true;
                }
            }
        }
        return false;
    }
}

class Solution {
    int dir[][] = {{0,1},{0,-1},{-1,0},{1,0}};
    int ans = 0;
    boolean dfs(int x,int y,char[][] board,String word,int[][] vis,int num){
        if(word.length() == 1){
            if(num == word.length()-1 ) return true;
        }
        else{
            if(num == word.length()-1 && word.charAt(num) == board[x][y]) return true;
        }
           
        for(int i = 0; i < 4; i++){
            vis[x][y] = 1;
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if(xx>=0&&xx<board.length&&yy>=0&&yy<board[0].length&&vis[xx][yy]==0&&board[x][y] == word.charAt(num)){
                if(dfs(xx,yy,board,word,vis,num+1)) return true;
            }
            vis[x][y] = 0;
        }
        return false;
    }

    public boolean exist(char[][] board, String word) {
        int x_len = board.length;
        int y_len = board[0].length;
        int vis[][] = new int[x_len][y_len];
        for(int i = 0; i < x_len; i++){
            for(int j = 0; j < y_len; j++){
                if(board[i][j] == word.charAt(0)){
                    if(dfs(i,j,board,word,vis,0)) ans = 1;
                }
            }
        }
        if(ans == 1) return true;
        else return false;
    }
}

这个代码更加直观简洁！！！！
class Solution {
    public boolean exist(char[][] board, String word) {
        int[][] visited = new int[board.length][board[0].length];
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    visited[i][j] = 1;
                    if (dfs(board, word, 1, i, j, visited)) return true;
                    visited[i][j] = 0;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int index, int i, int j, int[][] visited) {
        if (index == word.length()) {
            return true;
        }

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

作者：shi-san-dao
链接：https://leetcode-cn.com/problems/word-search/solution/tong-yong-dfs-by-shi-san-dao/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。