quick question. Why in the below code for 'word search' leetcode, does the code
if ( row not in range(rows) or
col not in range(columns) or
not work, while replacing it with
if ( row < 0 or row >= rows or
col < 0 or col >= columns or
work? The purpose is to see if the row and col is out of bounds of the matrix. Below is my full code.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
# Backtracking dfs
rows = len(board)
columns = len(board[0])
if 2 in range(2):
print('ye')
# Make sure not to visit same cell
path = set()
def dfs(row, col, ind):
if ind == len(word):
return True
# Check if out of bounds,
# or if we already visited this cell,
# or not right letter
if ( row not in range(rows) or ## DOESN'T WORK ##################
col not in range(columns) or ### STUCK IN INFINITE ##########
(row, col) in path or
board[row][col] != word[ind] ):
return False
# Otherwise, mark self as visited path, and
# call for all other directions
else:
path.add((row, col))
bottom = dfs(row + 1, col, ind + 1)
top = dfs(row - 1, col, ind + 1)
right = dfs(row, col + 1, ind + 1)
left = dfs(row, col - 1, ind + 1)
# Done with this layer, remove from visited
path.remove((row, col))
# Return True if any paths returned True
return bottom or top or right or left
for row in range(rows):
for col in range(columns):
# Start word with each letter to check
if dfs(row, col, 0): return True
return False
Thank you in advance.
EDIT: I used the following code for 'number of islands' leetcode, you can see below that range() is used successfully. so i don't know why it doesn't work in the above code.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
visited = set()
rows, columns = len(grid), len(grid[0])
islands = 0
def bfs(row, column):
# Store top, bottom, left, right directions
directions = [ [1, 0], [-1, 0], [0, 1], [0, -1] ]
# Already added to visited earlier
queue = [ (row, column) ]
while queue:
popped = queue.pop(0)
for [vertical, horizontal] in directions:
new_row = popped[0] + vertical
new_column = popped[1] + horizontal
new_point = (new_row, new_column)
# Before adding new point, check if
# point is within the grid's bounds,
# is equal to '1',
# and is not visited yet
#
# Cannot have new_row < rows and new_column < columns,
# then negative index would pass...
if (new_row in range(rows) and
new_column in range(columns) and
grid[new_row][new_column] == '1' and
new_point not in visited):
visited.add( (new_point) )
queue.append( new_point )
