剑指 Offer 12. 矩阵中的路径

剑指 Offer 12. 矩阵中的路径

给定一个 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

刚开始使用了dfs,

class Solution {
public:
    bool exist(vectorchar>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (board[i][j] == word[0]) {
                    if (Pan(i, j, board, word, 0))
                        return true;
                }
            }
        }
        return false;
    }
    bool Pan(int i, int j, vectorchar>> board, string word, int p) {
        board[i][j] = '1';
        if (p == (word.size() - 1))
            return true;
        if (i - 1 >= 0 && board[i - 1][j] == word[p + 1]) {
            if (Pan(i - 1, j, board, word, p + 1))
                return true;
        }
        if (i + 1 < board.size() && board[i + 1][j] == word[p + 1]) {
            if (Pan(i + 1, j, board, word, p + 1))
                return true;
        }
        if (j - 1 >= 0 && board[i][j - 1] == word[p + 1]) {
            if (Pan(i, j - 1, board, word, p + 1))
                return true;
        }
        if (j + 1 < board[i].size() && board[i][j + 1] == word[p + 1]) {
            if (Pan(i, j + 1, board, word, p + 1))
                return true;
        }
        return false;
    }
};

运行时间很慢，打败了5%的人，内存也打败了5%的人，我以为自己的方法有问题，后面看题解的方法，和我的方法类似，但是执行的效率很高，代码也很简洁

class Solution {
public:
    bool exist(vectorchar>>& board, string word) 
    {
        int row = board.size();
        int col = board[0].size();
        // vector> visited(row, vector(col));
        for(int i = 0; i < row; ++i)
        {
            for(int j = 0; j < col; ++j)
            {
                if(DFS(i, j, row, col, board,  word, 0))
                {
                    return true;
                }
            }
        }
        return false;
    }

    bool DFS(int i, int j, int row, int col, vectorchar>>& board,  string& word, int k)
    {
        // 终止条件
        // 越界或已访问过或长度已超过字符串长度或匹配失败
        if(i < 0 || i >= row || j < 0 || j >= col ||  board[i][j] != word[k])
        {
            return false;
        }
        if(k == word.size() - 1)
        {
            return true;
        }
        // visited[i][j] = true;
        board[i][j] = '\0';
 
        bool res = 
        DFS(i, j + 1, row, col, board,  word, k + 1) ||
        DFS(i, j - 1, row, col, board,  word, k + 1) || 
        DFS(i + 1, j, row, col, board,  word, k + 1) ||
        DFS(i - 1, j, row, col, board, word, k + 1);

        board[i][j] = word[k];
        return res;

    }

};

class Solution {
public:
    bool exist(vectorchar>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (board[i][j] == word[0]) {
                    if (Pan(i, j, board, word, 0))
                        return true;
                }
            }
        }
        return false;
    }
    bool Pan(int i, int j, vectorchar>> &board, string &word, int p) {
        board[i][j] = '1';
        if (p == (word.size() - 1))
            return true;
        if (i - 1 >= 0 && board[i - 1][j] == word[p + 1]) {
            if (Pan(i - 1, j, board, word, p + 1))
                return true;
        }
        if (i + 1 < board.size() && board[i + 1][j] == word[p + 1]) {
            if (Pan(i + 1, j, board, word, p + 1))
                return true;
        }
        if (j - 1 >= 0 && board[i][j - 1] == word[p + 1]) {
            if (Pan(i, j - 1, board, word, p + 1))
                return true;
        }
        if (j + 1 < board[i].size() && board[i][j + 1] == word[p + 1]) {
            if (Pan(i, j + 1, board, word, p + 1))
                return true;
        }
        board[i][j]= word[p];
        return false;
    }
};