题目描述

难度：中等

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

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

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

提示：

1 <= board.length <= 200
1 <= board[i].length <= 200
board 和 word 仅由大小写英文字母组成

思路

矩阵搜索问题，可以想到使用回溯的方式来做。

可以想到递归的每一步我们需要做的是，判断矩阵当前位置的值和目标串中此时迭代到的字符是否匹配，如果不匹配就返回false，反之对矩阵当前位置的其他相邻的位置做同样的操作。再加入边界和重复判断，就完成了。

代码

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }

        return false;
    }

    boolean dfs(char[][] board, String word, int i, int j, int k) {
        // 边界判断
        if (i < 0 || i >= board.length || j < 0 || j > board[0].length || board[i][j] != word.charAt(k)) return false;
        // 递归出口
        if (k == word.length() - 1) return true;

        // 标记避免重复
        board[i][j] = '\0';
        boolean res = dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i + 1, j, k + 1)
                || dfs(board, word, i, j - 1, k) || dfs(board, word, i, j + 1, k + 1);
        // 回溯恢复
        board[i][j] = word.charAt(k);

        return res;
    }
}