Please help me! Why TLE ? C++ code


  • 0
    H
    //I have saw all the discuss,but I can't solve my problem that TLE.
    class Solution {
    bool valid(int i,int j,int m,int n)
    {
    	if(i>=0&&i<m&&j>=0&&j<n) return true;
    	else return false;
    }
    void dfs(vector<vector<char>>&board,string &word,int row,int col,bool &res,int len)
    {
       if(len==word.size()) res=true;
       else  
      {
    	int m=board.size(),n=board[0].size();
    	int i=row,j=col;
    	if(valid(i-1,j,m,n)&&board[i-1][j]==word[len])
    	{
    		board[i-1][j]+=32;
    		dfs(board,word,i-1,j,res,len+1);
    		board[i-1][j]-=32;
    	}
    	if(valid(i+1,j,m,n)&&board[i+1][j]==word[len])
    	{
    		board[i+1][j]+=32;
    		dfs(board,word,i+1,j,res,len+1);
    		board[i+1][j]-=32;
    	}
    	if(valid(i,j-1,m,n)&&board[i][j-1]==word[len])
    	{
    		board[i][j-1]+=32;
    		dfs(board,word,i,j-1,res,len+1);
    		board[i][j-1]-=32;
    	}
    	if(valid(i,j+1,m,n)&&board[i][j+1]==word[len])
    	{
    		board[i][j+1]+=32;
    		dfs(board,word,i,j+1,res,len+1);
    		board[i][j+1]-=32;
    	}
      }
    }
    public:
    bool exist(vector<vector<char>>& board, string word) {
    	int m=board.size();
    	int n=board[0].size();
    	bool res=false;
    	int len=0;
    	for(int i=0;i<m;i++)
    	{
    		for(int j=0;j<n;j++)
    		{
    			if(board[i][j]==word[len])
    			{
                    board[i][j]+=32;
    				dfs(board,word,i,j,res,len+1);
    				board[i][j]-=32;
    			}
    			if(res==true)  return true;
    		}
    	}
    	return false;
    }
    };

Log in to reply
 

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