Any different between the two solution


  • 0
    W

    I propose a DFS solution and I got the TLE, I propose a DP solution and I got the TLE.
    Then I watch the dicsuss, I find that most of people use DFS got acceted. So I change my DFS and got accepted. Now I just want to ask any big difference between original my code and the changed my code.
    The first code is original and the second is changed code.And the second got ac.

    class Solution {
    public:
    bool exist(vector<vector<char> > &board, string word) {
    	for(int i = 0;i < board.size();i++) {
    		for(int j = 0;j < board[0].size();j++) {
    			if( board[i][j] == word[0]) {
    				//tmp datastruct indicator that points have visited
    			    vector<vector<bool> > visited(board.size(),vector<bool>(board[0].size(),false));
    				if( dfsstring(i, j, board, word,0,visited) )
    					return true;
    			}
    		}
    	}
    	return false;
    	
    }
    bool dfsstring(int i, int j, vector<vector<char> > &board, string word, int depth, vector<vector<bool> > &visited) {
    	//if equal
    	if(board[i][j] == word[depth]) {
    		//have visited
    	    visited[i][j] = true;
    		//have got the tail of the word
    		if( depth + 1 == word.length() )
    			return true;
    		int upx = i - 1;
    		int upy = j;
    		int downx = i + 1;
    		int downy = j;
    		int leftx = i;
    		int lefty = j - 1;
    		int rightx = i;
    		int righty = j + 1;
    		if( !outboard(upx,upy,board,visited) ) {
    			if( dfsstring(upx, upy, board, word, depth + 1,visited) )
    				return true;
    		}
    		if( !outboard(downx,downy,board,visited) ) {
    			if( dfsstring(downx, downy, board, word, depth + 1,visited) )
    				return true;
    		}
    		if( !outboard(leftx,lefty,board,visited) ) {
    			if( dfsstring(leftx, lefty, board, word, depth + 1,visited) )
    				return true;
    		}
    		if( !outboard(rightx,righty,board,visited) ) {
    			if( dfsstring(rightx, righty, board, word, depth + 1,visited) )
    				return true;
    		}
    		//canceled visited
    		visited[i][j] = false;
    	}
    	return false;
    }
    bool outboard(int i, int j, vector<vector<char> > &board, vector<vector<bool> > &visited) {
    	if(i >= board.size() || i < 0)
    		return true;
    	if(j >= board[0].size() || j < 0)
    		return true;
    	if(visited[i][j])
    	    return true;
    	return false;
    }
    

    };

    The changed code:

    class Solution {
    public:
    bool exist(vector<vector<char> > &board, string word) {
    	for(int i = 0;i < board.size();i++) {
    		for(int j = 0;j < board[0].size();j++) {
    			if( board[i][j] == word[0]) {
    			    vector<vector<bool> > visited(board.size(),vector<bool>(board[0].size(),false));
    				if( dfsstring(i, j, board, word,1,visited) )
    					return true;
    			}
    		}
    	}
    	return false;
    	
    }
    bool dfsstring(int i, int j, vector<vector<char> > &board, string &word, int depth, vector<vector<bool> > &visited) {
    	if( depth == word.length() )
    	    return true;
    	visited[i][j] = true;
    	int upx = i - 1;
    	int upy = j;
    	int downx = i + 1;
    	int downy = j;
    	int leftx = i;
    	int lefty = j - 1;
    	int rightx = i;
    	int righty = j + 1;
    	if( !outboard(upx,upy,board,visited) && board[upx][upy] == word[depth] ) {
    		if( dfsstring(upx, upy, board, word, depth + 1,visited) )
    			return true;
    	}
    	if( !outboard(downx,downy,board,visited) && board[downx][downy] == word[depth] ) {
    		if( dfsstring(downx, downy, board, word, depth + 1,visited) )
    			return true;
    	}
    	if( !outboard(leftx,lefty,board,visited) && board[leftx][lefty] == word[depth] ) {
    		if( dfsstring(leftx, lefty, board, word, depth + 1,visited) )
    			return true;
    	}
    	if( !outboard(rightx,righty,board,visited) && board[rightx][righty] == word[depth] ) {
    		if( dfsstring(rightx, righty, board, word, depth + 1,visited) )
    			return true;
    	}
    	visited[i][j] = false;
    	return false;
    }
    bool outboard(int i, int j, vector<vector<char> > &board, vector<vector<bool> > &visited) {
    	if(i >= board.size() || i < 0)
    		return true;
    	if(j >= board[0].size() || j < 0)
    		return true;
    	if(visited[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.