Word Search

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

• Mark the current cell as travelled before continuing.
• Use backtracking.

def exist(self, board, word):
    self.ROWS = len(board)
    self.COLS = len(board[0])
    self.board = board
 
    for row in range(self.ROWS):
        for col in range(self.COLS):
            if self.backtrack(row, col, word):
                return True
 
    # no match found after all exploration
    return False
 
def backtrack(self, row, col, suffix):
    # bottom case: we find match for each letter in the word
    if not suffix:
        return True
 
    # Check the current status, before jumping into backtracking
    if not (
        0 <= row < self.ROWS and
        0 <= col < self.COLS and
        self.board[row][col] == suffix[0]
    ):
        return False
 
 
    ret = False
    # mark the choice before exploring further.
    self.board[row][col] = "#"
    # explore the 4 neighbor directions
    for rowOffset, colOffset in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        ret = self.backtrack(row + rowOffset, col + colOffset, suffix[1:])
        # break instead of return directly to do some cleanup afterwards
        if ret:
            break
 
    # revert the change, a clean slate and no side-effect
    self.board[row][col] = suffix[0]
 
    # Tried all directions, and did not find any match
    return ret