Why DFS will be TLE in this kind of questions?


  • 0
    C

    Below is my code using DFS to solve the question, it gives right answers but will be TLE, can anyone tell me why? (DFS algorithm is always TLE in all "Unique Path" series questions)

    class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        
        if not obstacleGrid or not obstacleGrid[0]:
            return 0
        else:
            n,m=len(obstacleGrid),len(obstacleGrid[0])
            res=[]
            self.dfs(obstacleGrid, n, m, 0, 0, res)
            return sum(res)
            
    def dfs(self, obstacleGrid, n, m, i, j, res):
        if obstacleGrid[i][j]==1:
            return
        elif i==n-1 and j==m-1:
            res.append(1)
        else:
            if i<n-1:
                self.dfs(obstacleGrid, n, m, i+1, j, res)
            if j<m-1:
                self.dfs(obstacleGrid, n, m, i, j+1, res)

Log in to reply
 

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