Leetcode: Word Search
Given a matrix of characters, return True if the word is contained within the matrix by visiting horizontally and vertically adjacent fields.
The solution involves backtracking which means that we have to mark the character on the board as visited. In this case it is relatively simple as valid characters contain only [A-Z] so that we can take a - to mark a visited field and know that this will not appear in the word that we’re looking for.
Furthermore it helps to see the problem as a tree instead of a matrix. Once we find the first initial position (which there could be multiple of), select it as a root node and move from there left, right, up and down in any order. Once we found the first viable solution, we return True.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if word == '':
return True
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0]:
if self.inner(board, word, i, j):
return True
return False
def inner(self, board, word, i, j) -> bool:
if word == board[i][j]:
return True
char = word[0]
res = []
if board[i][j] == char:
# Replace character so we don't visit twice
board[i][j] = '-'
if j > 0:
res.append(self.inner(board, word[1:], i, j - 1))
if i > 0:
res.append(self.inner(board, word[1:], i - 1, j))
if i < len(board) - 1:
res.append(self.inner(board, word[1:], i + 1, j))
if j < len(board[0]) - 1:
res.append(self.inner(board, word[1:], i, j + 1))
# Backtrack
board[i][j] = char
return any(res)