Word Search - Leetcode Solution

Problem Statement:

Given a 2D grid of characters and a word, find if the 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:

Input: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]

word = "ABCCED"

Output: true

Solution:

To solve this problem, we can use a backtracking algorithm. The general idea is to start at each cell in the grid, and check if it is the starting letter of the word we are trying to find. If it is, we continue searching for the rest of the word by checking neighboring cells.

The algorithm can be implemented as follows:

1. Create a boolean 2D grid to keep track of which cells we have visited.
2. For each cell in the 2D grid, check if it is the starting letter of the word. If it is, start the recursive search function.
3. In the recursive function, check if the current cell matches the current letter in the word. If it does, mark the current cell as visited, and continue searching for the rest of the word by checking neighboring cells.
4. If we find the entire word, return true. Otherwise, backtrack to the previous cell and try a different neighboring cell.
5. If we have tried all neighboring cells and still haven't found the word, mark the current cell as unvisited and return false.

The time complexity of this algorithm is O(MN4^L), where M is the number of rows in the grid, N is the number of columns in the grid, and L is the length of the word. This is because we visit every cell in the grid (M*N), and for each cell, we check up to 4 neighboring cells (4), and we do this for each letter in the word (L).

The space complexity is O(L), where L is the length of the word, because we use a recursive call stack to keep track of each letter in the word as we search for it in the grid.

Code:

Here is the Python 3 code for the algorithm:

class Solution: def exist(self, board: List[List[str]], word: str) -> bool: if not board: return False

    m, n = len(board), len(board[0])
    
    for i in range(m):
        for j in range(n):
            if self.dfs(board, i, j, word):
                return True
            
    return False

def dfs(self, board, i, j, word):
    if not word:
        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
    
    temp = board[i][j]
    board[i][j] = '$'
    
    res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:])
    
    board[i][j] = temp
    
    return res

The “exist” method takes the 2D grid and the word we are searching for as input, and returns True if the word exists in the grid, and False otherwise.

The “dfs” method is the recursive function used to search for the word. It takes as input the current cell (i, j), the remaining word we are searching for, and the grid. It returns True if the word is found, and False otherwise.

We start by checking if the remaining word is empty. If it is, we have found the entire word, and return True.

Next, we check if the current cell is out of bounds, or if it doesn't match the current letter in the word. If either of these conditions is true, we return False.

Otherwise, we mark the current cell as "$" to indicate that it has been visited, and continue our search for the rest of the word by recursively calling the “dfs” method on each neighboring cell, with the remaining word. If any of these recursive calls return True, we have found the word, and we return True. Otherwise, if none of the recursive calls return True, we backtrack by marking the current cell as unvisited (by setting it back to its original character), and return False.

Finally, in the “exist” method, we loop through each cell in the grid, and call the “dfs” method on each cell. If any of these calls return True, we have found the word, and we return True. Otherwise, if none of the calls return True, we return False.

1