Python solution with detailed explanation

  • 0


    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
                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

Log in to reply

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