Sword finger offer 12 Path in matrix

Power button 79
Please design a function , Used to determine whether there is a path containing all characters of a string in a matrix . The path can start from any lattice in the matrix , Each step can be left in the matrix 、 Right 、 On 、 Move down one space . If a path passes through a lattice of a matrix , Then the path cannot enter the grid again . for example , In the following 3×4 The matrix of contains a string “bfce” The path of （ The letters in the path are bold ）.

[[“a”,“b”,“c”,“e”],
[“s”,“f”,“c”,“s”],
[“a”,“d”,“e”,“e”]]

But the matrix doesn't contain strings “abfb” The path of , Because the first character of the string b After occupying the first row and the second lattice in the matrix , The path can't go into this grid again .

Example 1：

Input ：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
Output ：true

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;
    }
};

Time complexity O(MN)
Spatial complexity O(K)