LeetCode79. Word Search

1、题目链接

https://leetcode.com/problems/word-search/

2、解题思路

这道题的意思是给你一个二维的字符数组，然后是否能从里面按照顺序找到一些字符组成某一个字符串，这么说有点绕口，直接看示例：

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

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

如上面所示，你可以从任意一个字符开始，然后从它的上下左右方向顺序拼接，如果最终能找到可以拼接成目标字符串的话，返回true，否则返回false；这种目测一下就知道用深搜来做，因为这种类型之前做过实在是很多，就不多做介绍了，代码如下：

代码

class Solution {
    public boolean exist(char[][] board, String word) {
        if (null == board || null == word || board.length == 0 || word.equals("")) {
            return false;
        }

        int colLen = board.length;
        int rowLen = board[0].length;

        boolean[][] visited = new boolean[colLen][rowLen];  //剪枝，为了过滤重复访问的节点
        String nowWord = "";  //自己组成一个目标数组
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (word.startsWith(String.valueOf(board[i][j]))) {
                    nowWord = "";
                    if (dfs(board, visited, i, j, nowWord, word)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }
    
    public boolean dfs(char[][] board, boolean[][] visited, int i, int j, String nowWord, String word) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length) {
            return false;
        }
        if (visited[i][j]) {
            return false;
        }
        nowWord += String.valueOf(board[i][j]);
        if (!word.startsWith(nowWord)) {
            return false;
        }
        if (word.equals(nowWord)) {
            return true;
        }
        visited[i][j] = true;
        // 从某个点的上下左右四个方向依次递归搜索
        if (dfs(board, visited, i - 1, j, nowWord, word)) {
            return true;
        }
        if (dfs(board, visited, i + 1, j, nowWord, word)) {
            return true;
        }
        if (dfs(board, visited, i, j - 1, nowWord, word)) {
            return true;
        }
        if (dfs(board, visited, i, j + 1, nowWord, word)) {
            return true;
        }
        visited[i][j] = false;
        return false;
    }
}

结果

1565356911788.jpg