原题

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

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

示例:

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

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

解法

思想

因为同一个位置的字符不能用两次，得标记，dfs回溯的时候必须把标记清除。

代码

class Solution {
    char[][] board;
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        for(int i = 0;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                visited = new boolean[board.length][board[0].length];
                if(dfs(i,j,word)) return true;
            }
        }
        return false;
    }

    public boolean dfs(int x,int y,String word){
        if(word.length()==1){
            if(word.charAt(0)==board[x][y]) return true;
        } 
        if(word.charAt(0)!=board[x][y]) return false;
        visited[x][y] = true;
        boolean ans = false;
        //向上
        if(x-1>=0 && !visited[x-1][y]) ans = ans||dfs(x-1,y,word.substring(1));
        //向下
        if(x+1<board.length && !visited[x+1][y]) ans = ans||dfs(x+1,y,word.substring(1));
        //向左
        if(y-1>=0 && !visited[x][y-1]) ans = ans||dfs(x,y-1,word.substring(1));
        //向右
        if(y+1<board[0].length && !visited[x][y+1]) ans = ans||dfs(x,y+1,word.substring(1));
        //清除标记
        if(ans == false) visited[x][y] = false;
        return ans;
    } 
}

下面是利用短路或剪枝后的版本，按理说更快，leetcode测试也差不多：

class Solution {
    char[][] board;
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        for(int i = 0;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                visited = new boolean[board.length][board[0].length];
                if(dfs(i,j,word)) return true;
            }
        }
        return false;
    }

    public boolean dfs(int x,int y,String word){
        if(word.length()==1){
            if(word.charAt(0)==board[x][y]) return true;
        } 
        if(word.charAt(0)!=board[x][y]) return false;
        visited[x][y] = true;
        //向上
        if(x-1>=0 && !visited[x-1][y]) if(dfs(x-1,y,word.substring(1))) return true;
        //向下
        if(x+1<board.length && !visited[x+1][y]) if(dfs(x+1,y,word.substring(1))) return true;
        //向左
        if(y-1>=0 && !visited[x][y-1]) if(dfs(x,y-1,word.substring(1))) return true;
        //向右
        if(y+1<board[0].length && !visited[x][y+1]) if(dfs(x,y+1,word.substring(1))) return true;
        //清除标记
        visited[x][y] = false;
        return false;
    } 
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode79-%e5%8d%95%e8%af%8d%e6%90%9c%e7%b4%a2/