Word Search

December 18, 2023

Problem #

Given a 2D board of letters and a target word, find all occurrences of the word in the board.

Solution #

Below is the complete Python code for the function find_word_occurrences, which finds all occurrences of a given word in a 2D board of letters. You can use this code in your Python environment:

def find_word_occurrences(board, word):
    if not board or not word:
        return []

    def dfs(board, word, index, x, y):
        if index == len(word):
            return True
        if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or board[x][y] != word[index]:
            return False

        temp = board[x][y]
        board[x][y] = "#"  # Mark as visited
        found = (dfs(board, word, index + 1, x + 1, y) or
                 dfs(board, word, index + 1, x - 1, y) or
                 dfs(board, word, index + 1, x, y + 1) or
                 dfs(board, word, index + 1, x, y - 1))
        board[x][y] = temp  # Backtrack
        return found

    occurrences = []
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == word[0] and dfs(board, word, 0, i, j):
                occurrences.append((i, j))

    return occurrences

# Example usage
board = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E']
]
word = "ABCCED"
occurrences = find_word_occurrences(board, word)
print("Occurrences of the word:", occurrences)

This code defines the find_word_occurrences function along with an example usage. When you run this code, it will search for the specified word in the given 2D board and print the starting positions of all its occurrences.

Solution Analysis: Step by Step #

To solve the problem of finding all occurrences of a target word in a 2D board of letters, we can use a depth-first search (DFS) algorithm. The approach involves searching each cell of the board and, if the first letter matches the first letter of the word, we recursively explore its neighboring cells (up, down, left, right) to see if the subsequent letters match the next letters of the word.

Here’s a Python function that implements this solution:

1. Function Description:

   • exist(board, word): Main function to find all occurrences of the word in the board.
   • dfs(board, word, index, x, y): Helper function for depth-first search starting from a given cell.

2. Algorithm Steps:

   • Iterate through each cell of the board.
   • If the first letter of the word matches the letter in the cell, call the DFS helper function.
   • Mark the cell as visited by replacing the letter with a special character (e.g., '#') to avoid revisiting it in the same path.
   • After returning from the DFS call, restore the original letter in the cell (backtracking).

3. DFS Function:

   • Checks if the current index of the word matches the letter in the current cell.
   • Recursively calls itself for neighboring cells if the subsequent letters match.

Let’s implement this algorithm in Python.

The Python function successfully found the occurrences of the word “ABCCED” in the given 2D board of letters. In this example, the word occurs starting at position (0, 0) in the board. This position represents the row and column index where the first letter of the word is found.

You can use this function with different boards and words to find all occurrences of a specific word in a 2D letter board. The function returns a list of tuples, where each tuple (i, j) represents the starting position (row i and column j) of an occurrence of the word in the board.