大家好！我是曾续缘💫
今天是《LeetCode 热题 100》系列
发车第 60 天
回溯第 6 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给定一个 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 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
难度：💖💖

解题方法

这道题需要在一个字符网格中查找给定的单词。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是水平或垂直相邻的单元格。

遍历整个字符网格，找到与单词第一个字母匹配的起始位置。
从起始位置开始进行回溯搜索，尝试在相邻的位置匹配单词的下一个字母。
使用回溯算法，在搜索过程中标记已经访问过的单元格，避免重复访问。

Code

查看代码

java

class Solution {
    int[] d = new int[]{-1, 0, 1, 0, -1};
    boolean ans = false;
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == word.charAt(0)){
                    char tmp = board[i][j];
                    board[i][j] = '0';
                    backtrack(board, word, 1, i, j);
                    board[i][j] = tmp;
                    if(ans){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private void backtrack(char[][] board, String word, int cur, int i, int j){
        if(cur == word.length()){
            ans = true;
            return;
        }
        int m = board.length, n = board[0].length;
        for(int k = 0; k < 4; k++){
            int di = i + d[k], dj = j + d[k + 1];
            if(di < 0 || di >= m || dj < 0 || dj >= n || board[di][dj] != word.charAt(cur)){
                continue;
            }
            char tmp = board[di][dj];
            board[di][dj] = '0';
            backtrack(board, word, cur + 1, di, dj);
            board[di][dj] = tmp;
            if(ans){
                return;
            }
        }
    }
}

查看代码

var dirs = []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}

func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    var dfs func(int, int, int) bool 
    dfs = func(i, j, k int) bool {
        if board[i][j] != word[k] {
            return false
        }
        if k == len(word) - 1 {
            return true
        }
        board[i][j] = 0
        for _, d := range dirs {
            x, y := i+d.x, j+d.y
            if 0 <= x && x < m && 0 <= y && y < n && dfs(x, y, k+1) {
                return true
            }
        }
        board[i][j] = word[k]
        return false
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dfs(i, j, 0) {
                return true
            }
        }
    }
    return false
}

解题方法 ​

Code ​

解题方法

Code