题目描述

题解

深度优先遍历

这道题最直观的思路就是深度优先搜索, 从一个位置出发, 向四周搜索, 寻找到一条合适的道路一直到底.

为了降低时间复杂度, 要对搜索的过程进行剪枝:

如果碰到了边界, 返回false
如果该位置已经搜索过, 返回false
如果该位置与目标字符不匹配, 返回false

对题目的理解有一点需要注意, 首先要做的是找到目标字符串的起点, 然后按照顺序逐个搜索, 如果考虑找到了目标字符串中的某个字符就开始搜索, 将会大大增加算法的复杂程度, 给思路造成障碍.

所以遍历整个矩阵的流程就是:

寻找words[0]的字符
一旦找到就从此位置开始进行深度优先搜索
- 如果目标字符全部匹配, 返回true
- 否则, 返回false
遍历完整个矩阵, 返回false

在深度优先搜索的递归过程中, 若当前字符匹配, 准备进行下一步的搜索, 需要将该位置标记, 换成#或任意不是字母的字符, 当再次搜索到该位置时, 就会因为字符不匹配而返回false

一开始我创建了一个布尔矩阵专门用来记录已经搜索过的位置, 其实不需要的, 换成#后将其转换成字符不匹配的问题, 降低思维难度和空间复杂度

但是一定要注意回溯, 不然会影响到其他的搜索过程

public class jz12 {

    int rows;
    int cols;

    public boolean exist(char[][] board, String word) {
        if (board.length == 0) {
            return false;
        }
        char[] charArray = word.toCharArray();

        rows = board.length;
        cols = board[0].length;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(board, i, j, charArray, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, char[] charArray, int k) {
        if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != charArray[k]) {
            return false;
        }
        if (k == charArray.length - 1) {
            return true;
        }
        char temp = board[i][j];
        board[i][j] = '#';
        boolean res = dfs(board, i + 1, j, charArray, k + 1) ||
                dfs(board, i - 1, j, charArray, k + 1) ||
                dfs(board, i, j + 1, charArray, k + 1) ||
                dfs(board, i, j - 1, charArray, k + 1);

        board[i][j] = temp;
        return res;
    }
}