Word search
July 24, 2022
backtrackingProblem URL: Word search
We will run dfs on each element of the board, if we find a character match, then we move forward and search for next character in all 4 directions.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
ROWS, COLS = len(board), len(board[0])
path = set()
def dfs(r: int, c: int, i: int) -> bool:
if i == len(word):
return True
if (
r < 0
or c < 0
or r >= ROWS
or c >= COLS
or word[i] != board[r][c]
or (r, c) in path
):
return False
path.add((r, c))
res = (
dfs(r + 1, c, i + 1)
or dfs(r - 1, c, i + 1)
or dfs(r, c + 1, i + 1)
or dfs(r, c - 1, i + 1)
)
path.remove((r, c))
return res
for r in range(ROWS):
for c in range(COLS):
if dfs(r, c, 0):
return True
return False
Time Complexity: O(n*m*4^n)
Space Complexity: O(n*m)