My 19ms accepted C++ code


  • 41
    P
       class Solution {
        public:
        	 bool exist(vector<vector<char> > &board, string word) {
        		 m=board.size();
        		 n=board[0].size();
                for(int x=0;x<m;x++)
                    for(int y=0;y<n;y++)
                    {
        				if(isFound(board,word.c_str(),x,y))
        					return true;
                    }
                return false;
            }
        private:
        	int m;
        	int n;
            bool isFound(vector<vector<char> > &board, const char* w, int x, int y)
            {
        		if(x<0||y<0||x>=m||y>=n||board[x][y]=='\0'||*w!=board[x][y])
        			return false;
                if(*(w+1)=='\0')
                    return true;
        		char t=board[x][y];
        		board[x][y]='\0';
        		if(isFound(board,w+1,x-1,y)||isFound(board,w+1,x+1,y)||isFound(board,w+1,x,y-1)||isFound(board,w+1,x,y+1))
        			return true; 
        		board[x][y]=t;
                return false;
            }
        };

  • 4
    G

    Great work! But the board is destroyed.


  • 1
    L

    I have a similar solution but it isn't as clean as yours. I use another 2D array to record the route.

    class Solution {
    public:

    bool helper(int statr,int statc,vector<vector<char> > &board,string word, vector<vector<bool> > &route){
        
        if(word == "") return true;
        
        int rows = board.size();
        int cols = board[0].size();
        
        route[statr][statc]=true;
        
        
        while(statr <rows && statc <cols){
            //up
            if(statr-1>=0 && !route[statr-1][statc] && word[0] == board[statr-1][statc])
                if(helper(statr-1,statc,board,word.substr(1,word.length()-1), route)) 
                    return true;
                else {
                    
                    route[statr-1][statc] = false; 
                }
            //down
            if(statr+1<rows && !route[statr+1][statc] && word[0] == board[statr+1][statc])
                if(helper(statr+1,statc,board,word.substr(1,word.length()-1), route)) 
                    return true;
                else {
                    
                    route[statr+1][statc] = false; 
                }
            //left
            if(statc-1>=0 && !route[statr][statc-1] && word[0] == board[statr][statc-1])
                if(helper(statr,statc-1,board,word.substr(1,word.length()-1), route)) 
                    return true;
                else {
                    
                    route[statr][statc-1] = false; 
                }
            //right
            if(statc+1<cols && !route[statr][statc+1] && word[0] == board[statr][statc+1])
                if(helper(statr,statc+1,board,word.substr(1,word.length()-1), route)) 
                    return true;
                else {
                    
                    route[statr][statc+1] = false; 
                }
            break;
        }
        
        return false;
    }
    
    bool exist(vector<vector<char> > &board, string word) {
        
        if(word == "") return true;
        if(board.empty()) return false;
        
        int rows = board.size();
        int cols = board[0].size();
        
        vector<vector<bool> >route(rows, vector<bool>(cols,false));
        
        for(int i=0; i<rows; ++i)
        {
            for(int j=0; j<cols; j++)
            {
                if(board[i][j] == word[0])
                    if(helper(i,j,board,word.substr(1,word.length()-1),route))
                        return true;
                    else route[i][j]=false;
            }
        }
        
        return false;
    }
    

    };


  • 0
    L

    not as faster as the above, right?


  • 1
    M

    Why the "while" and then "break" instead of "if"?


  • 0
    X

    Good solution! I am just wonder how you test the running time of your solution? under which enviroment? Thanks!


  • 0
    C

    I don't think so.. It will be recover when "board[x][y]=t;" after the sub-recursion.
    "board[x][y]='\0';" is just for the judgement that board[x][y]=='\0' in "if(x<0||y<0||x>=m||y>=n||board[x][y]=='\0'||*w!=board[x][y])".


  • 1
    L

    You are right. I should use if instead~


  • 0
    L

    My code is easy to understand but can not as fast and clean as the above one.


  • 0
    L

    Mine? After you submit your code, you can press the details button and it will show the running time.


  • 0
    P

    Actually he is right. If the word is successfully found, the data of the table will be changed and cannot be used again for another search.


  • 0
    J

    i guess setting it to t before returning 'true' solves the problem


  • 0
    C

    Yes U are right. It is a interesting bug, but it can be fixed by the next comment said easily...


  • 0
    C

    Yeah, I think you are right !~


  • 0
    Z
    This post is deleted!

  • 0
    R

    can you please mention space and time complexity?


  • 0
    4

    Just store the result in bool and recover the board and then return the bool instead of directly returning the function call.


  • 0
    S

    My accepted non-recursive backtrace solution using stack:

    https://discuss.leetcode.com/topic/53468/ac-non-recursive-backtrace-solution-with-stack


  • 0
    J

    I found a really strange problem is, when I delete the "&" in the function isFound, the runtime will exceed the limit, is there anyone knows why is this? the answer is still correct but takes much more time.


  • 0
    G

    @greenup

    class Solution {
    private:
        vector<vector<char>> boardTemp;
        string wordTemp;
    public:
        bool exist(vector<vector<char>>& board, string word) {
            boardTemp=board;
            wordTemp=word;
            if(boardTemp.size()==0)return false;
            if(word.compare("")==0)return true;
            for(int i=0;i<boardTemp.size();i++){
                for(int j=0;j<boardTemp[i].size();j++)
                    if(check(i,j,0)) return true;
            }
            return false;
        }
        
        bool check(int x,int y,int start){
            if(start>=wordTemp.size())return true;
            if(x<0||x>=boardTemp.size()||y<0||y>=boardTemp[x].size())return false;
            if(boardTemp[x][y]!=wordTemp[start])return false;
            char c=boardTemp[x][y];
            boardTemp[x][y]='$';//Read
            if(check(x-1,y,start+1)||check(x+1,y,start+1)||check(x,y-1,start+1)||check(x,y+1,start+1))
                return true;
            boardTemp[x][y]=c;
            return false;
        }
    };

Log in to reply
 

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