# Python solution with detailed explanation

• Solution

Word Search https://leetcode.com/problems/word-search/

Standard Backtracking Algorithm

• There are MN possible starting states and a valid state (i,j) must satisfy board[i,j] = word[0].
• Terminating condition is k == len(word)
• While generating the next candidates we have to make sure we are not revisiting a visited state. You use a table to mark visited positions or you can modify the board. The next state must be unvisited and equal to word[k]
``````class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0]:
ch, board[i][j] = board[i][j], -1
if self.backtrack(ch, 1, word, board, i, j):
return True
board[i][j] = ch
return False

def backtrack(self, ch, k, word, board, x, y):
if k == len(word):
return True
else:
for x1,y1 in ((x+1,y), (x-1,y), (x, y+1), (x, y-1)):
if 0<=x1<len(board) and 0<=y1<len(board[0]) and board[x1][y1] == word[k]:
ch, board[x1][y1] = board[x1][y1], -1
if self.backtrack(ch, k+1, word, board, x1, y1):
return True
board[x1][y1] = ch
return False
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.