My 28ms C++ solution ,only one method.


  • 1
    B
    bool exist(vector<vector<char>>& board, string word,pair<int,int>location=pair<int,int>(-1,-1)) {
    	if (word.length()==0)
    		return true;
    	int i = location.first;
    	int j = location.second;
    	if (location.first==-1&&location.second==-1)
    	{
    		for (i = 0; i < board.size(); i++)
    			for (j = 0; j < board[i].size(); j++)
    				if (board[i][j] == word[0])
    					if (exist(board, word, pair<int, int>(i, j)))
    						return true;
    		return false;
    	}
    	char initChar = board[i][j]; board[i][j] = '*';
    	if (word.length() > 1)
    	{
    		int direction[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    
    		for (int k = 0; k < 4; k++) {
    			int ii = i + direction[k][0];
    			int jj = j + direction[k][1];
    			if (ii >= 0 && ii < board.size() && jj >= 0 && jj < board[i].size() && board[ii][jj] == word[1])
    				if (exist(board, word.substr(1, word.size()), pair<int, int>(ii, jj)))
    					return true;
    		}
    		board[i][j] = initChar;
    		return false;
    	}
    	return true;
    }

  • 0
    C

    I almost have the same approach but mine seems to be timing out. I can't figure out why. Here is my code -

        bool helper(vector<vector<char>>& board,string word,int pos,int i,int j,vector<vector<bool>>& visited){
        if(pos>=word.size())
            return true;
        visited[i][j]=true;
        if(i-1>=0 && !visited[i-1][j] && board[i-1][j]==word[pos] && helper(board,word,pos+1,i-1,j,visited)){
            return true;
        }
        if(i+1<board.size() && !visited[i+1][j] && board[i+1][j]==word[pos] && helper(board,word,pos+1,i+1,j,visited)){
            return true;
        }
        if(j-1>=0 && !visited[i][j-1] && board[i][j-1]==word[pos] && helper(board,word,pos+1,i,j-1,visited)){
            return true;
        }
        if(j+1<board[0].size() && !visited[i][j+1] && board[i][j+1]==word[pos] && helper(board,word,pos+1,i,j+1,visited)){
            return true;
        }
        return false;
        
    }
    bool exist(vector<vector<char>>& board, string word) {
        
        if(board.size()==0){
            return word=="";
        }
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(),false));
                if(board[i][j]==word[0]){
                     if(helper(board,word,1,i,j,visited))
                        return true;
                }
            }
        }
        return false;
            
    }

  • 0
    J

    u forgot to set visited[i][j] = false;


  • 0

    in function helper(), you can use string &word instead of string word.


Log in to reply
 

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