【回溯专题】剑指 Offer 12. 矩阵中的路径-跟着帅地玩副业，开拓第二曲线PlayOffer

sincere 普通 2023年9月11日下午11:34

思路：dfs递归+回溯
复杂度：时间复杂度O(3^kmn)，空间复杂度O(n)

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(board,words,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        // 超过边界或不相等时结束判断
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) {
            return false;
        }
        // 完全匹配了
        if (k == word.length - 1) {
            return true;
        }
        // 标记已访问
        board[i][j] = '\0';
        // dfs 遍历四边
        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 + 1) || dfs(board, word, i, j - 1, k + 1);
        // 回溯
        board[i][j] = word[k];
        return res;
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年9月9日下午3:06

dsf，一个visited数组记录访问过的节点

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

        char[] words = word.toCharArray();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(dfs(board, words, i, j, 0, visited)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, char[] words, int i, int j, int k, int[][] visited){
        if(i<0 || i>=board.length || j<0 || j>= board[0].length){
            return false;
        }
        // 之前访问过则直接返回
        if(visited[i][j] == 1){
            return false;
        }
        if(board[i][j] != words[k]){
            return false;
        }
        // 字符串遍历完毕
        if(k == words.length-1){
            return true;
        }
        visited[i][j] = 1;
        boolean up = dfs(board, words, i-1, j, k+1, visited);
        boolean down = dfs(board, words, i+1, j, k+1, visited);
        boolean left = dfs(board, words, i, j-1, k+1, visited);
        boolean right = dfs(board, words, i, j+1, k+1, visited);

        visited[i][j] = 0;
        return up || down || left || right;
    }
}

0 赞同 0 条回复

塔底的仰望永久会员 2023年9月9日下午2:46

dfs

class Solution {
    private int m;
    private int n;
    private boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].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;
    }

    public boolean dfs(char[][] board, int row, int col, String word, int depth) {
        if (visited[row][col]) {
            return false;
        }
        if (board[row][col] != word.charAt(depth)) {
            return false;
        }
        if (word.length() - 1 == depth) {
            return true;
        }
        visited[row][col] = true;
        // 遍历当前阶段的解
        for (int i = - 1; i <= 1; i++) {
            for (int j =- 1; j <=+ 1; j++) {
                if (i + row < m && i + row >= 0 && j + col >= 0 && j + col < n && i !=j && i != -j ) {
                    if(dfs(board, i + row, j + col, word, depth + 1)) {
                        return true;
                    }
                }
            }
        }
        visited[row][col] = false;
        return false;
    }
}

0 赞同 0 条回复

小肸永久会员 2023年9月8日下午12:01

class Solution {
    //最多调用row * col次dfs()函数，每一次dfs()函数的时间复杂度为O(3 ^ k)，
    //所以总时间复杂度为O(3^k * row * col)
    //空间复杂度为O(len(word))，递归深度最多为len(word),最坏情况len(word) = row * col，此时word的长度最长
    public boolean exist(char[][] board, String word) {
        int row = board.length, col = board[0].length;
        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < col; j ++) {
                if (dfs(board, word.toCharArray(), i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (i < 0 || i >= board.length || j < 0 || 
            j >= board[0].length || board[i][j] != word[k]) {
            return false;
        }
        //k == word.length - 1，说明word的最后一个字符已经在board中找到
        if (k == word.length - 1) {
            return true;
        }
        //标记这个位置已经访问过
        board[i][j] = ' ';
        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 + 1) || dfs(board, word, i, j - 1, k + 1);
        //回溯
        board[i][j] = word[k];
        return res;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年9月7日下午4:58

// 从矩阵的第一个元素开辟dfs匹配
// 如果没有元素匹配成功，则false，如果有匹配成功的true

class Solution {
public:
    bool dfs(vector<vector<char>>& board,int i,int j,int n,int m,string& word,int k)
    {
        if(i>=n||i<0||j>=m||j<0||board[i][j]!=word[k]) return false;
        if(k==word.size()-1) return true;
        board[i][j] = '\n';
        bool res = dfs(board,i+1,j,n,m,word,k+1)||dfs(board,i-1,j,n,m,word,k+1)||dfs(board,i,j+1,n,m,word,k+1)||dfs(board,i,j-1,n,m,word,k+1);
        board[i][j] = word[k];
        return res;
    }
    bool exist(vector<vector<char>>& board, string& word) {
        if(!board.size()) return false;
        int n = board.size();
        int m = board[0].size();
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                if(dfs(board,i,j,n,m,word,0)) return true;
            }
        }
        return false;
    }
};

0 赞同 0 条回复

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

共以下 5 个回答

# 回答此问题取消回复

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

共以下 5 个回答

# 回答此问题 取消回复

# 回答此问题取消回复