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