c++ dfs solution


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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.