0

I'm doing the leetcode #79. In the def dfs(), I must use x < 0 or x >= size to check if x is out of range. Using x not in range(size) to check seems to take longer time and it will cause a Time Limit Exceeded error. Why does it take longer time?

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        path = set()
        rowSize = len(board)
        colSize = len(board[0])
        
        def dfs(x,y,i):
            if i==len(word):
                return True
            # This will cause Time Limit Exceeded error
            # if (x not in range(rowSize) or
            #     y not in range(colSize) or
            #     board[x][y] != word[i] or
            #     (x,y) in path):
            #     return False
            
            # But this works
            if (x < 0 or y < 0 or
               x >= rowSize or y >= colSize or
               board[x][y] != word[i] or (x,y) in path) :
                return False
            
            path.add((x,y))
            res = (dfs(x+1,y,i+1) or 
                   dfs(x-1,y,i+1) or
                   dfs(x,y+1,i+1) or
                   dfs(x,y-1,i+1))
            path.remove((x,y))
            return res
        
        for i in range(rowSize):
            for j in range(colSize):
                if dfs(i,j,0):
                    return True
        return False
John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Victor W
  • 1
  • 2
  • 1
    I thought `in range` is quite fast: https://stackoverflow.com/questions/30081275/why-is-1000000000000000-in-range1000000000000001-so-fast-in-python-3 – j1-lee Feb 27 '22 at 05:43
  • Yeah but LC doesn't let me do it that way – Victor W Feb 27 '22 at 05:47
  • Maybe you're running a Python 2 interpreter. – Mateen Ulhaq Feb 27 '22 at 05:47
  • What time are you getting with the original? If it’s just on the edge of acceptable, very minor differences like the overhead of constructing a `range` object, the method calls involved, and the greater flexibility of `range`’s `in` (e.g. non-1 step sizes require division) could make the difference. – Ry- Feb 27 '22 at 05:49
  • @MateenUlhaq: Doesn’t support type annotations. – Ry- Feb 27 '22 at 05:49
  • @Ry- I got 8994 ms runtime, I think you're right – Victor W Feb 27 '22 at 05:55

0 Answers0