Leetcode题解剑指 Offer 12. 矩阵中的路径

PROBLEM

难度中等

MY ANSWER

使用DFS与回溯解决，矩阵visit表示搜索中是否走过该格子，index代表当前需要匹配的字符串的字符。dfs(int i, int j, int index)表示从matrix(i, j)出发能否搜索到从索引k开始的word(k, -1)。执行时：

当前字符不匹配，直接返回false；
当前字符匹配且已经是末尾，直接返回true；
当前字符匹配但不是末尾，将当前格子设置为访问过。递归遍历未访问过的相邻格子，若相邻格子中的dfs有返回true，则返回true，否则返回false。这一步返回前要将当前格子设置为未访问，进行回溯。

时间复杂度O(MN3^K)，K为字符串长度，但由于剪枝，时间复杂度并不会这么大。空间复杂度O(MN)，开销用于visit矩阵。

class Solution {
public:
    vector<vector<char>> matrix;
    vector<vector<int>> visit;
    string str;
    bool dfs(int i, int j, int index) {
        if(matrix[i][j] != str[index]) {
            return false;
        }
        else if(index == str.size() - 1) {
            return true;
        }
        visit[i][j] = 1;
        if(i + 1 < matrix.size() && !visit[i + 1][j]) {
            if(dfs(i + 1, j, index + 1)) {
                visit[i][j] = 0;
                return true;
            }
        }
        if(j + 1 < matrix[0].size() && !visit[i][j + 1]) {
            if(dfs(i, j + 1, index + 1)) {
                visit[i][j] = 0;
                return true;
            }
        }
        if(i - 1 >= 0 && !visit[i - 1][j]) {
            if(dfs(i - 1, j, index + 1)) {
                visit[i][j] = 0;
                return true;
            }
        }
        if(j - 1 >= 0 && !visit[i][j - 1]) {
            if(dfs(i, j - 1, index + 1)) {
                visit[i][j] = 0;
                return true;
            }
        }
        visit[i][j] = 0;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        vector<int> tmp;
        matrix = board;
        str = word;
        visit.resize(matrix.size());
        for(int i = 0; i < matrix.size(); i++) {
            visit[i].resize(matrix[0].size());
        }
        for(int i = 0; i < matrix.size(); i++) {
            for(int j = 0; j < matrix[0].size(); j++) {
                if(matrix[i][j] == str[0]) {
                    if(dfs(i, j, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

BETTER SOLUTION

代码更简洁，且没有使用visit矩阵，而是将原矩阵的字符进行更改。但如果像我的代码这样先找到第一个匹配的字符再调用dfs，运行时间会更少。时间复杂度O(MN3^K)，空间复杂度O(K)。

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

SUMMARY

注意递归中回溯的设计，在递归前进行设置，最后递归调用结束后返回前还原设置，如题目中visit的设置。