C++ Solution using Backtracking


  • 8
    C
    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) {
            if(board.size()==0 || board[0].size()==0 )
                return true;
            
            for(int i=0; i<board.size(); i++){
                for(int j=0; j<board[0].size(); j++){
                    if(check(board, word, i, j))
                        return true;
                }
            }
            return false;
        }
        
        bool check(vector<vector<char>>& board, string word, int i, int j){
            if(word.length()==0)
                return true;
            if(i<0 || j<0 ||i>=board.size() ||j>=board[0].size())
                return false;
            if(word[0]==board[i][j]){
                char c = word[0];
                board[i][j]='\0';
                if(check(board,word.substr(1), i+1, j)||
                    check(board,word.substr(1), i-1, j)||
                    check(board,word.substr(1), i, j+1)||
                    check(board,word.substr(1), i, j-1))
                    return true;
                board[i][j]=c;
            }
            return false;
        }
    };

  • 0
    C

    nice,please help me and translate a little。Thanks


Log in to reply
 

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