My simple c++ solution


  • 0

    class Solution {
    /* just try to enjoy (:)*/
    public:
    int height,width;

    bool isFound(vector<vector<char>>&board,const string& str,int x,int y,vector<vector<bool>>& accepted){
      
        if(str.length()==0) return true;
        bool bottom=false,up=false,right=false,left=false;
        if(x+1<height&&accepted[x+1][y]&&board[x+1][y]==str[0]){
            accepted[x+1][y]=false;
            bottom=isFound(board,str.substr(1,str.length()-1),x+1,y,accepted);
            accepted[x+1][y]=true;
        }
        if(!bottom&& x-1>=0&&accepted[x-1][y]&&board[x-1][y]==str[0]){
            accepted[x-1][y]=false;
            up=isFound(board,str.substr(1,str.length()-1),x-1,y,accepted);
            accepted[x-1][y]=true;
        }
        if(!bottom&&!up&& y-1>=0&&accepted[x][y-1]&&board[x][y-1]==str[0]){
            accepted[x][y-1]=false;
            left=isFound(board,str.substr(1,str.length()-1),x,y-1,accepted);
            accepted[x][y-1]=true;
        }
        if(!bottom&&!up&&!left&& y+1<width&&accepted[x][y+1]&&board[x][y+1]==str[0]){
            accepted[x][y+1]=false;
            right=isFound(board,str.substr(1,str.length()-1),x,y+1,accepted);
            accepted[x][y+1]=true;
        }
        return bottom||up||left||right;
    }
    bool exist(vector<vector<char>>& board, string word) {
        height=board.size();
        width=board[0].size();
        vector<vector<bool>> a(height,vector<bool>(width,true));
     
        for(int i=0;i<height;i++){
            for(int j=0;j<width;j++){
                if(board[i][j]==word[0]) {
                  
                a[i][j]=false;
                   
                    if(isFound(board,word.substr(1,word.length()-1),i,j,a)) return true;
                    
                a[i][j]=true;
                }
            }
        }
    
        return false;
    }
    

    };


Log in to reply
 

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