Word Search - Python Solution

1. Introduction

The "Word Search" problem is an engaging puzzle that involves navigating through a grid of characters to form a specific word. This problem is an excellent example of using depth-first search (DFS) and backtracking to explore complex data structures. It's a common challenge in coding interviews, testing one's ability to implement search algorithms on multi-dimensional arrays.

Problem

Given an m x n grid of characters board and a string word, the task is to return true if the word can be constructed from letters of sequentially adjacent cells in the grid. Adjacent cells are those that are horizontally or vertically neighboring. The same letter cell may not be used more than once.

2. Solution Steps

1. Traverse each cell in the grid.

2. For each cell, use a DFS approach to search for the word.

3. During the search, mark the cell as visited and then backtrack after the search.

4. Check for the validity of the path at each step.

5. Return true if the word is found, otherwise false.

3. Code Program

def exist(board, word):
    def dfs(row, col, index):
        # Check if we have found the word
        if index == len(word):
            return True
        # Check the boundary conditions and whether the cell matches the letter in the word
        if (row < 0 or col < 0 or row >= len(board) or col >= len(board[0]) or
                word[index] != board[row][col] or visited[row][col]):
            return False
        # Mark the cell as visited
        visited[row][col] = True
        # Explore all possible directions: up, down, left, right
        found = (dfs(row + 1, col, index + 1) or
                 dfs(row - 1, col, index + 1) or
                 dfs(row, col + 1, index + 1) or
                 dfs(row, col - 1, index + 1))
        # Backtrack and unmark the cell
        visited[row][col] = False
        return found

    visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]
    for row in range(len(board)):
        for col in range(len(board[0])):
            if dfs(row, col, 0):
                return True
    return False

# Example Test Cases
print(exist([['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], "ABCCED"))  # True
print(exist([['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], "SEE"))     # True
print(exist([['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], "ABCB"))   # False

Output:

True
True
False

Explanation:

1. DFS Function: The dfs function is used to explore the grid. It checks if the current cell is part of the word.

2. Boundary and Match Check: The function checks if the current cell is within the grid boundaries and matches the current letter in word.

3. Visited Marking: The cell is marked as visited to avoid using it more than once in the search.

4. Directional Search: The search continues in all four possible directions (up, down, left, right).

5. Backtracking: After exploring all directions, the function backtracks by unmarking the cell as visited.

6. Iterative Search: The main function iterates over each cell in the grid, starting a DFS search from each cell.

7. Result: The function returns true if the word is found, otherwise false.