当前位置：
  1. 首页
  2. 剑指offer刷题第二期
  3. 问题详情

【回溯专题】剑指 Offer 12. 矩阵中的路径

本问题对应课程链接：剑指offer刷题第二期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路
2、给出时间和额外空间复杂度

shuaidi
124 14

共以下 14 个回答

  • Gg 普通 2023年7月31日 下午11:54 
    class Solution {

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

    public boolean dfs(int i, int j, char[][] board, int k, char[] words){
        // 剪枝情况
        if( i < 0 || j < 0 || 
        i >= board.length || j >= board[0].length || board[i][j] != words[k]){
                return false;
            }
        // 找到最后一个元素了
        if(k == words.length - 1){
            return true;
        }
        // 标记当前元素已使用
        board[i][j] = '\0';
        // 继续递归周围可能正确
        boolean res = 
         dfs(i + 1,j, board, k+1,words) ||
         dfs(i,j+1, board, k+1,words) || 
         dfs(i-1,j, board, k+1,words) || 
         dfs(i,j-1, board, k+1,words);
        board[i][j] = words[k];
        return res;
    }
}
    0 赞同 0 条回复
  • 宁 永久会员 2023年3月17日 下午7:18

    回溯算法，1word是字符串 2注意边界值有没有等号，有没有-1

    class Solution {
    public boolean exist(char[][] board, String word) {
        //选择可以开始的一个格子，回溯法继续搜索上下左右四个位置
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(backTracing(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
    public boolean backTracing(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 = backTracing(board, word, i - 1, j, k + 1)||backTracing(board, word, i + 1, j, k + 1)
                    ||backTracing(board, word, i, j - 1, k + 1)||backTracing(board, word, i, j + 1, k + 1);
        board[i][j] = word.charAt(k);
        return res;
    }
}
    0 赞同 0 条回复
  • PatNick 普通 2023年1月17日 下午5:22 
    class Solution:
    def __init__(self):
        self.n = 0
        self.m = 0
        # self.visitedList = []
    def exist(self, board: list[list[str]], word: str) -> bool:
        self.n = len(board)
        self.m = len(board[0])
        # self.visitedList = [[False for _ in range(self.m)] for __ in range(self.n)]
        # 用两层for循环固定单词的第一个值
        for i in range(self.n):
            for j in range(self.m):
                if self.dfs(board,i,j,word,0):
                    return True

        return False

    def dfs(self,board,i,j,word,k):
        '''
        深度优先遍历
        Args:
            board:
            i，j：定位board的索引
            word:
            k: 固定word中的第k个元素
        '''

        # 终止条件
        # 不越界，未走过，值相等
        # if i < 0 or i >= self.n or j < 0 or j >= self.m or self.visitedList[i][j] or board[i][j] != word[k]:
        # 这里由于在原list中进行标记
        if i < 0 or i >= self.n or j < 0 or j >= self.m or board[i][j] != word[k]:
            return False

        if k == len(word)-1:
            return True
        # 对已经走过的路径进行标注
        # self.visitedList[i][j] = True

        # 也可以不使用一个专门的二维列表标记路径，而是直接在原列表中将这个元素改成一个不可能是答案的数来作为标记
        board[i][j] = '~~~'

        # 遍历每个阶段的可选解集合(规定方向是右，下，左，上)
        res = self.dfs(board,i,j+1,word,k+1) or self.dfs(board,i+1,j,word,k+1) or self.dfs(board,i,j-1,word,k+1) or self.dfs(board,i-1,j,word,k+1)

        # 回溯，需要去掉原来走过的路径的标记
        # self.visitedList[i][j] = False

        # 如果不用布尔list标记路径，在回溯时，就需要恢复原列表中的该元素，这里能等于word【k】是因为能够回溯说明之前这个位置的值是对的
        board[i][j] = word[k]
        return res
    0 赞同 0 条回复
  • lucca 普通 2023年1月16日 下午6:13

    回溯

    • 时间复杂度O(NM)
    • 空间复杂度O(NM)
    class Solution {

    private int[] dx = {0, 1, 0, -1}, dy = {-1, 0, 1, 0};
    private int n, m, k;
    private boolean[][] vis;
    private char[][] g;
    private String word;
    public boolean exist(char[][] board, String word) {
        this.n = board.length;
        this.m = board[0].length;
        this.g = board;
        this.k = word.length();
        this.word = word;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == word.charAt(0)) {
                    vis = new boolean[n][m];
                    vis[i][j] = true;
                    if (dfs(i, j, 1)) return true;
                }
            }
        }
        return false;
    }


    private boolean dfs(int i, int j, int cnt) {
        if (cnt == k) return true;

        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < n && 
                y >= 0 && y < m && 
                !vis[x][y] && g[x][y] == word.charAt(cnt)) {
                vis[x][y] = true;
                if (dfs(x, y, cnt + 1)) return true;
                vis[x][y] = false;
            }
        }
        return false;
    }
}
    0 赞同 0 条回复
  • @ 普通 2022年12月13日 下午7:52

    时间复杂度：O(MN)

    空间复杂度：O(K)

    class Solution {
    private int row;
    private int col;

    public boolean exist(char[][] board, String word) {
        this.row = board.length;
        this.col = board[0].length;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(dfs(board, word, i, j, 0))
                    return true;

            }
        }

        return false;

    }

    public boolean dfs (char[][] board, String word, int i, int j, int k) {

        if(i < 0 || i >= row || j < 0 || j >= col || 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, j + 1, k + 1) ||
                dfs(board, word, i + 1, j, k + 1) ||
                dfs(board, word, i, j - 1, k + 1) ||
                dfs(board, word, i - 1, j, k + 1);

        board[i][j] = word.charAt(k);


        return res;

    }
}
    0 赞同 0 条回复
  • 派大星 普通 2022年12月2日 下午9:04 
    public class Solution {
    int row, col;
    int len;
    boolean[][] visited;

    /**
     * dfs
     * 时间复杂度：O(3^k)
     * 空间复杂度：O(mn)
     */
    public boolean exist(char[][] board, String word) {
        this.row= board.length;
        this.col = board[0].length;
        this.len = word.length();
        visited = new boolean[row][col];

        // 遍历矩阵中的每一个元素并用dfs搜索
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dfs(board, word, i, j,0)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean dfs(char[][] board, String word, int i, int j,  int k){
        // 1. 剪枝
        // 数组出界 或 当前矩阵元素与目标字符不同 或 已访问过
        if(i < 0 || i >= row || j < 0 || j >= col || visited[i][j] || board[i][j] != word.charAt(k)){
            return false;
        }
        // 字符串已匹配成功
        if(k == len - 1){
            return true;
        }

        // 2. 选择此阶段其中一个解，将其加入到已选解集合中
        visited[i][j] = true;

        // 3. 进入下一阶段
        boolean res = dfs(board, word, i, j + 1, k + 1) ||
                dfs(board, word, i + 1, j, k + 1) ||
                dfs(board, word, i, j - 1, k + 1) ||
                dfs(board, word, i - 1, j, k + 1);

        // 4. 回溯
        visited[i][j] = false;

        return res;
    }
}
    0 赞同 0 条回复
  • 你有点可爱喔 普通 2022年11月30日 下午2:33 
    class Solution {
    int n;
    int m;
    int len;
    boolean [][] visited;
    public boolean exist(char[][] board, String word) {
        this.n = board.length;
        this.m = board[0].length;
        this.len = word.length();
        visited = new boolean[n][m];
        //我好像有思路
        for (int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(dfs(board,i,j,word,0)){
                    return true;
                }
            }
        }
        return false;
    }
    boolean dfs(char[][] board,int i,int j,String word,int k){
        if (i<0 || i>= n ||j<0 || j>= m || board[i][j] != word.charAt(k)){
            return false;
        }
        //如果匹配到最后一个字符
        if(k == len-1){
            return true;
        }
       // visited[i][j] = true;
        board[i][j] = '\n';
        boolean res =   dfs(board,i,j+1,word,k+1)||
                        dfs(board,i+1,j,word,k+1)||
                        dfs(board,i,j-1,word,k+1)||
                        dfs(board,i-1,j,word,k+1);
        board[i][j] = word.charAt(k);
        return res;
    }
}
    0 赞同 0 条回复
  • T 普通 2022年11月29日 下午4:47 
    class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(backtrace(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }

    public boolean backtrace(char[][] board, char[] word, int i, int j, int k) {
        // 超过边界或者该位置字母不等于word[k]都返回false
        if(i >= board.length || j >= board[0].length || i<0 || j<0 || board[i][j] != word[k])
            return false;
        if(k == word.length - 1) 
            return true;
        board[i][j] = '\0';
        boolean res = backtrace(board, word, i + 1, j ,k + 1) || backtrace(board, word, i, j + 1, k + 1) ||
                        backtrace(board, word, i - 1, j, k + 1) || backtrace(board, word, i, j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}
    0 赞同 0 条回复
  • 庄重 普通 2022年11月23日 下午3:16 
    // 思路：
//     1.这次的思路还是很清晰的，但是对于深度优先遍历的细节方面还需要掌握
//     2.主要流程中，对board中的每一个字符都进行遍历
//     3.确定一个任意某个字符后，进入深度遍历，遍历顺序 上->右->下—>左
//     4.中间遇到不符合word的字符进行回溯，回溯时对该路径上的标记变为未访问状态
//     5.直到找到word的末尾或者所有字符都作为第一个字符遍历过了
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size();
        m = board[0].size();
        len = word.length();
        //使用vector二维数组的构造函数和匿名对象对visited进行赋值，即完成了初始化又开辟了空间。
        //使用二级指针或者vector的resize方法总是会需要用到循环开辟空间和循环赋值
        visited = vector<vector<bool>>(n,vector<bool>(m,false));

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

    }
    //dsf：深度优先遍历
    bool dsf(vector<vector<char>>& board,int i, int j, string& word, int k){
        //越界或者访问过的或者不符合的返回false
        if(i < 0 || i >= n || j < 0 || j >= m || visited[i][j] || board[i][j] != word.at(k)){
            return false;
        }
        //word到结尾了
        if(k == len -1)
            return true;
        visited[i][j] = true;
        //遍历顺序 上->右->下—>左
        bool ret = dsf(board, i+1, j, word, k+1) || 
                    dsf(board, i, j+1, word, k+1) ||
                    dsf(board, i-1, j, word, k+1) ||
                    dsf(board, i, j-1, word, k+1);

        visited[i][j] = false;
        return ret;
    }
    int n;
    int m;
    int len;
    vector<vector<bool>> visited;
};
//时间复杂度O(nm + 3^k) nm个起点， 深度遍历的k个字符
//空间复杂度O(k) 深度遍历的k个字符
    0 赞同 0 条回复
  • 西西弗斯的石头 永久会员 2022年11月22日 下午12:51

    时间复杂度O（3 ^ k *mn）,空间复杂度为O（1）

    class Solution {
    int m;
    int n;
    int len;
    public boolean exist(char[][] board, String word) {
        len = word.length();
        m = board.length;
        n = board[0].length;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(dfs(board,i,j,word,0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board,int i,int j,String word,int k){
        if(i < 0||i >= m||j<0||j >= n||board[i][j] != word.charAt(k)) return false;
        if(k + 1 == len) return true;
        board[i][j] = '/';
        boolean res = dfs(board,i+1,j,word,k+1) || dfs(board,i-1,j,word,k+1) || dfs(board,i,j+1,word,k+1) ||
        dfs(board,i,j-1,word,k+1);
        board[i][j] = word.charAt(k);

        return res;
    }
}
    0 赞同 0 条回复
  • Tolkien 永久会员 2022年11月21日 下午10:43 
    public class Solution {
    int row, col;
    int len;
    boolean[][] visited;

    /**
     * dfs
     * 时间复杂度：O(3^k)
     * 空间复杂度：O(mn)
     */
    public boolean exist(char[][] board, String word) {
        this.row= board.length;
        this.col = board[0].length;
        this.len = word.length();
        visited = new boolean[row][col];

        // 遍历矩阵中的每一个元素并用dfs搜索
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dfs(board, word, i, j,0)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean dfs(char[][] board, String word, int i, int j,  int k){
        // 1. 剪枝
        // 数组出界 或 当前矩阵元素与目标字符不同 或 已访问过
        if(i < 0 || i >= row || j < 0 || j >= col || visited[i][j] || board[i][j] != word.charAt(k)){
            return false;
        }
        // 字符串已匹配成功
        if(k == len - 1){
            return true;
        }

        // 2. 选择此阶段其中一个解，将其加入到已选解集合中
        visited[i][j] = true;

        // 3. 进入下一阶段
        boolean res = dfs(board, word, i, j + 1, k + 1) ||
                dfs(board, word, i + 1, j, k + 1) ||
                dfs(board, word, i, j - 1, k + 1) ||
                dfs(board, word, i - 1, j, k + 1);

        // 4. 回溯
        visited[i][j] = false;

        return res;
    }
}
    0 赞同 0 条回复
  • So 普通 2022年11月21日 下午12:56 
    class Solution {
    int m;
    int n;
    int len;
    public boolean exist(char[][] board, String word) {
        this.m = board.length;
        this.n = board[0].length;
        this.len = word.length();
        visited = 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)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean dfs(char[][] board, int i, int j, String word, int k) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word.charAt(k)) {
            return false;
        }
        if (k == len - 1) {
            return true;
        }
        board[i][j] = '\n';
        boolean res = dfs(board, i, j + 1, word, k + 1) ||
                      dfs(board, i + 1, j, word, k + 1) ||
                      dfs(board, i, j - 1, word, k + 1) ||
                      dfs(board, i - 1, j, word, k + 1);
        board[i][j] = word.charAt(k);
        return res;
    }
}

    时间：O(mn * n ^ len)，空间：O(mn)

    0 赞同 0 条回复
  • 青木 普通 2022年11月20日 下午11:31 
    /**
    将原来的矩阵的字符变成空，然后恢复，这个记录是否已访问的方法有点妙
    主要思想就是遍历整个矩阵，再在四个方向上进行深度优先搜索

    时间O(m*n*3^k)
    空间O(k)
 */

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(backtrack(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }

    public boolean backtrack(char[][] board, char[] words, int i, int j , int k){
        if(i<0 || j>=board[0].length || i>=board.length || j<0 || board[i][j] != words[k]){
            return false;
        }
        if(k == words.length-1) return true;

        board[i][j] = '\0';
        boolean res = backtrack(board, words, i+1, j, k+1) || backtrack(board,words, i-1, j, k+1) ||
                    backtrack(board, words, i, j+1, k+1) || backtrack(board, words, i, j-1, k+1);
        board[i][j] = words[k];
        return res;
    }
}
    0 赞同 0 条回复
  • 訁訁訁訁訁 普通 2022年11月20日 下午11:13

    dfs

    时间复杂度：O(3^K * MN) ： 最差情况下，需要遍历矩阵中长度为 K 字符串的所有方案，时间复杂度为 O(3^K)；矩阵中共有 MN 个起点，时间复杂度为 O(MN)

    空间复杂度O(mn)

    class Solution {
    boolean[][] visited;
    int len;
     int m,n;
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        len = word.length();
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(dfs(board,i,j,0,word)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,int i,int j,int k,String word){
        if(i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word.charAt(k)){
            return false;
        }
        if(k == len - 1) return true;
        visited[i][j] =  true;
        boolean res =  dfs(board,i+1,j,k+1,word)||
               dfs(board,i,j+1,k+1,word)||
               dfs(board,i-1,j,k+1,word)||
               dfs(board,i,j-1,k+1,word);
        visited[i][j] = false;
        return res;
    }
}
    0 赞同 0 条回复

# 回答此问题

后才能回答