Always TLE (Has been solved)


  • 0
    E

    I use a visited member to save the node status, but I got Time Limit Exceed every time, so I change the way saving the node status, JUST using the board variable!

    class Solution {
    public:
    bool exist(vector<vector<char>>& board, string word)
    {
    	bool result = false;
    	for (int i = 0; i < board.size(); ++i)
    	{
    		for (int j = 0; j < board[0].size(); ++j)
    		{
    			std::vector<std::vector<bool>> visited(board.size(), std::vector<bool>(board[0].size(), false));
    			result = false;
    			search(board, i, j, visited, word, 0, result);
    			if (result)
    				return true;
    		}
    	}
    	
    
    	return result;
    }
    private:
    void search(std::vector<std::vector<char>> &board, int x, int y, std::vector<std::vector<bool>> &visited, const string &word, int index, bool &result)
    {
        if (index == word.length())
    	{
    		result = true;
    		return;
    	}
    	
    	if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || visited[x][y] == true)
    		return ;
    
    	if (board[x][y] == word[index])
    	{
    		visited[x][y] = true;
    		index++;
    		if (index == word.length())
    		{
    			result = true;
    			return ;
    		}
    
    		search(board, x + 1, y, visited, word, index, result);
    		if (result)
    			return;
    		search(board, x - 1, y, visited, word, index, result);
    		if (result)
    			return;
    		search(board, x, y + 1, visited, word, index, result);
    		if (result)
    			return;
    		search(board, x, y - 1, visited, word, index, result);
    	}
    }
    };

Log in to reply
 

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