I was attempting the word search problem here on leetcode. Leetcode seems to give me an error for the two test cases:
board = [["a","a"]], word = "aa"
and for : board = [["a"]], word = "a"
But the following code seems to work fine on Google colab for both of these test cases. Could someone be able to please pinpoint the exact cause? Likely, it is the result of the difference in Python versions. But what exactly is a loss for me! Thanks in advance!
class Solution:
def exist2(self, board: List[List[str]], word: str, current_row, current_col,\
match_index=0,seen_cells=[]) -> bool:
if match_index==len(word):
return True
else:
for i in range(-1,2):
for j in range(-1,2):
if current_row+i>=0 and current_col+j>=0 and current_row+i<len(board)\
and current_col+j<len(board[0]) and\
board[current_row+i][current_col+j]==word[match_index] and\
(current_row+i,current_col+j) not in seen_cells\
and i+j!=-2 and i+j!=2:
match_index+=1
seen_cells.append((current_row+i,current_col+j))
if self.exist2(board, word, current_row+i, current_col+j,\
match_index,seen_cells):
return True
else:
seen_cells.remove((current_row+i,current_col+j))
current_row,current_col=seen_cells[-1]
return False
def exist(self, board: List[List[str]], word: str, current_row=0, current_col=0,\
match_index=0,seen_cells=[]) -> bool:
start_index=[]
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j]==word[0]:
start_index.append((i,j))
for ele in start_index:
if self.exist2(board, word, ele[0],ele[1]):
return True
return False
def main()
print(exist([["a","a"]],'a'))
There are multiple issues with your code.
First, you are relying on the default argument of seen_cells, but there is only one instance of that list, which is used across all calls to exist2. Multiple test cases will share the same state, which causes problems when there are tuples in seen_cells from previous calls of exist2.
You are also incrementing match_index in every iteration of the inner loop in exist2 even though each iteration should be independent. You should instead pass match_index + 1 to the recursive call of exist2.
Furthermore, you have allowed diagonal moves by only checking i+j!=-2 and i+j!=2. For instance, the move (-1, 1) is allowed since -1 + 1 = 0 is neither equal to -2 nor 2. It would be correct to check that exactly one of i and j is non-zero. This can be done concisely with ((not i) ^ (not j)), though you can also write it out more explicitly.
In addition, you do not add the first cell in the path to seen_paths. You can fix this off-by-one error by checking for the match right at the start of exist2 and remove from seen_cells right before the return. Note that the line current_row,current_col=seen_cells[-1] does not make much sense and can cause IndexErrors; remove it.
Finally, this solution is too slow because checking for existence in a list is a linear time operation. Instead, use a set or a boolean matrix to mark which cells have already been passed through.