this returns time limit, because
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
rows = len(board)
cols = len(board[0])
visited = set()
def dfs(row, col, word_idx=0):
# if word_idx is equal to the length of word
# we could assume that we find the complete word
if word_idx == len(word):
return True
# if borders is passed
# row is lower than 0 or col is lower than 0
# or if row > len(rows) or if cols > len(cols) this will index overflow, so this is not ok
if row < 0 or col < 0 or row >= rows or col >= cols:
return False
if word[word_idx] != board[row][col]:
return False
if ((row,col) in visited):
return False
visited.add((row,col))
# we should choice the path that contains the right letter
# so we need to check up ^ (row - 1, 0, word_idx + 1)
# so we need to check down (row + 1, 0, word_idx + 1)
# so we need to check right -> (row, col + 1, word_idx + 1)
# so we need to check left <- (row, col - 1, word_idx + 1)
found = (
dfs(row - 1, col, word_idx + 1) or
dfs(row + 1, col, word_idx + 1) or
dfs(row, col + 1, word_idx + 1) or
dfs(row, col - 1, word_idx + 1)
)
visited.remove((row,col))
# if find return the result of the paths
return found
for row in range(rows):
for col in range(cols):
if dfs(row,col):
return True
return False
#["A","B","C","E"]
#["S","F","E","S"]
#["A","D","E","E"]
#ABCB
#["C","A","A"]
#["A","A","A"]
#["B","C","D"]
#AAB
#["A","B","C","E"]
#["S","F","E","S"]
#["A","D","E","E"]
# ABCESEEEFS
this returns time limit, under the hood this is hashmap
set()
this check cost o(1), because (row, col) is the key of hash
if ((row,col) in visited):
return False
this addition cost o(1) to be added, but o(N) when the hash should be resized
visited.add((row,col))
this remove cost(1) too,
visited.remove((row,col))