Depth-First Search

April 9, 2024

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED” Output: true

Solution:

depth-first search (DFS) to explore all possible paths in the grid to find the word:

def check_exist_dfs(board, word):
    def dfs(board, i, j, word):
        if len(word) == 0:  # Base case: the entire word is found
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[0]:
            return False  # Out of bounds or current cell does not match the first character of the word

        temp = board[i][j]  # Temporarily mark the current cell as visited
        board[i][j] = '#'  # '#' is used to indicate visited cells

        # Check adjacent cells
        found = dfs(board, i + 1, j, word[1:]) or dfs(board, i - 1, j, word[1:]) or \
                dfs(board, i, j + 1, word[1:]) or dfs(board, i, j - 1, word[1:])

        board[i][j] = temp  # Restore the current cell value

        return found

    # Start DFS from each cell
    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(board, i, j, word):
                return True

    return False


if __name__ == '__main__':
    board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
    word = "ABCCEDFS"
    print(check_exist_dfs(board, word))
    # Output: True

In the dfs function, perform depth-first search starting from each cell in the grid, checking if the word can be found starting from that cell. We recursively explore all possible paths from the current cell, marking visited cells to avoid revisiting them.