We try finding the word one character at a time starting from every cell avoiding already visited cells.
Say 
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def find(r, c, i):
nonlocal m, n
if i == len(word):
return True
if not (0 <= r < m) or not (0 <= c < n):
return False
if board[r][c] != word[i]:
return False
curr_char = board[r][c]
board[r][c] = "#"
for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
if find(r + dr, c + dc, i + 1):
board[r][c] = curr_char
return True
board[r][c] = curr_char
return False
for r in range(m):
for c in range(n):
if find(r, c, 0):
return True
return False
Follow up: Could you use search pruning to make your solution faster with a larger board?
We start searching with a word character that appears the least in the board, in that way we exit early.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
count_of = {}
for r in range(m):
for c in range(n):
if board[r][c] not in count_of:
count_of[board[r][c]] = 1
else:
count_of[board[r][c]] += 1
if count_of.get(word[-1], 0) < count_of.get(word[0], 0):
word = word[::-1]
def find(r, c, i):
if i == len(word):
return True
if not (0 <= r < m and 0 <= c < n):
return False
if board[r][c] != word[i]:
return False
curr_char = board[r][c]
board[r][c] = "#"
for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
if find(r + dr, c + dc, i + 1):
board[r][c] = curr_char
return True
board[r][c] = curr_char
return False
for r in range(m):
for c in range(n):
if find(r, c, 0):
return True
return False
unreasonably effective 
Leave a comment