leetcode79. 单词搜索

题目

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

示例 2：

输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE”
输出：true

示例 3：

输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB”
输出：false  

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search

题解

很典型的dfs题，这个类型的题目应该在很短的时间得出思路AC。

结束条件是遍历完所有单词，一个节点有四个方向遍历，即上、下、左、右，往这四个方向递归遍历，得到任一条满足条件路径返回即可。

class Solution {

    //防止回环，遍历过的节点打一个标志，不可再访问。
    private boolean[][] v;

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

    public boolean dfs(char[][] board,int i,int j,String word,int cur,int m,int n){
        //结束条件是遍历完word
        if(cur==word.length()){
            return true;
        }
        boolean res = false;
        //边界和标志处理
        if(i>=0 && i<m && j>=0 && j<n && !v[i][j]){
            v[i][j] = true;
            //单词匹配成功继续递归
            if(board[i][j]==word.charAt(cur)){
                //只要有一条路径满足即返回true，用逻辑与
                res =dfs(board,i+1,j,word,cur+1,m,n) || 
                    dfs(board,i,j+1,word,cur+1,m,n) || 
                    dfs(board,i-1,j,word,cur+1,m,n) ||
                    dfs(board,i,j-1,word,cur+1,m,n);
            }
            //回溯后将节点去掉标志，回溯后该节点可能还需要访问
            v[i][j]=false;
        }
        return res;
    }
}