79. Word Search

79. Word Search#

Difficulty: Medium

Link to Problem: To see the Word Search problem on LeetCode, click here!

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.

Constraints:

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Probelm Explanation:#

The problem is to determine whether a given word can be constructed from characters in an m x n grid of characters. The word can be formed by moving sequentially through horizontally or vertically neighboring cells in the grid, and you cannot use the same cell more than once.

Here are the specifics of the problem:

You are given an m x n grid, which is a 2D board of characters.
You are also given a string word consisting of lowercase and uppercase English letters.
Your task is to determine if the word can be found in the grid by moving from one cell to an adjacent cell (horizontally or vertically) and collecting the characters sequentially to form the word.
You can’t use the same cell more than once when forming the word.
If it’s possible to form the word in the grid, return True; otherwise, return False.

For example, consider the following grid and word:

board = [["A", "B", "C", "E"],
         ["S", "F", "C", "S"],
         ["A", "D", "E", "E"]]         
word = "ABCCED"

In this case, the word “ABCCED” can be formed by moving through the cells (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,3) in the grid. Therefore, the function should return True.

Conversely, if the word is impossible to construct, such as in the case of the word “ABCB” for the same grid, where there’s no valid path that forms the word, the function should return False.

The problem involves searching for a path through the grid that matches the characters in the word while respecting the constraints mentioned. It can be solved using depth-first search (DFS) or backtracking.

Solution:#

Here’s a Python function to implement this algorithm:

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            # Check if the current position is out of bounds or doesn't match the character in the word.
            if not (0 <= i < len(board)) or not (0 <= j < len(board[0])) or board[i][j] != word[k]:
                return False
            
            # If we have matched all characters in the word, return True.
            if k == len(word) - 1:
                return True

            # Temporarily mark the current cell to prevent revisiting.
            tmp, board[i][j] = board[i][j], "/"

            # Explore adjacent cells by making recursive calls in all four directions.
            found = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)

            # Restore the original character in the cell.
            board[i][j] = tmp

            return found

        # Iterate through all cells in the board.
        for i in range(len(board)):
            for j in range(len(board[0])):
                # Check if the 'dfs' function starting from this cell returns True.
                if dfs(i, j, 0):
                    return True

        # If no match is found after exploring all cells, return False.
        return False

Explanation:#

Import the necessary module:
- from typing import List: This line imports the List type from the typing module, which is used to specify the type of the board parameter in the method signature.
Define the Solution class:
- class Solution:: This line defines a class called Solution to encapsulate the solution for the word search problem.
Define the exist method:
- def exist(self, board: List[List[str]], word: str) -> bool:: This method is a member of the Solution class and takes two parameters: board, which is a 2D list of characters, and word, which is a string. It returns a boolean value, indicating whether the word exists in the board.
Implement the inner dfs function:
- def dfs(i, j, k):: This is a helper function used for depth-first search (DFS). It is called recursively to explore the board and search for the word. It takes three parameters: i and j representing the current position on the board, and k representing the current index in the word string.
- Inside dfs, it checks if the current position is out of bounds or if the character at the current position on the board does not match the character at the current index in the word. If either of these conditions is met, it returns False.
- If k is equal to the length of the word minus one, it means we have successfully matched all characters in the word, so it returns True.
- The function then temporarily replaces the character at the current position with a marker, “/”, to prevent revisiting the same cell. It then explores adjacent cells by making recursive calls in all four directions: up, down, left, and right. If any of these recursive calls return True, it propagates the True result up the call stack. After the exploration is complete, it restores the original character in the cell.
Iterate through the board:
- The outer loop iterates through all cells in the board using two nested loops. For each cell, it checks if the dfs function starting from that cell (with k initially set to 0) returns True. If it does, it means the word exists, so the method returns True.
Return False:
- If the loop completes without finding the word in the board, the method returns False.

To use this code, you can create an instance of the Solution class and call the exist method on that instance, passing the board and the word as arguments to check if the word exists in the board.

Test cases:#

Here’s how you can use this solution:

# Example 1: 

# Create an instance of the Solution class
solution = Solution()

# Test case 1: Word "ABCCED" can be found in the grid
board1 = [["A","B","C","E"],
          ["S","F","C","S"],
          ["A","D","E","E"]]
word1 = "ABCCED"
print(solution.exist(board1, word1))  # Expected output: True

True

# Example 2

# Test case 2: Word "SEE" can be found in the grid
word2 = "SEE"
print(solution.exist(board1, word2))  # Expected output: True

True

# Example 3

# Test case 3: Word "ABCB" cannot be found in the grid
word3 = "ABCB"
print(solution.exist(board1, word3))  # Expected output: False

False

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the exist method in the given code.

Time Complexity:

The primary work in this code is done by the dfs function, which performs a depth-first search through the grid. The time complexity of the dfs function is \(O(4^(n))\), where “n” is the length of the word. This is because, in the worst case, the function explores all possible directions (up, down, left, right) for each character in the word.

The outer loops iterate through all cells in the board, which has dimensions m x n. So, the total number of iterations of dfs is O(m * n). However, since the dfs function has a higher time complexity, the overall time complexity is still dominated by the dfs function.

Therefore, the overall time complexity of the exist method is \(O(m * n * 4^n)\), where “m” and “n” are the dimensions of the board, and “n” is the length of the word.

Space Complexity:

The primary space usage comes from the recursive calls in the dfs function. The depth of the recursion can be at most equal to the length of the word, which is O(n).
Additionally, the tmp variable and the recursive calls on the call stack consume a small amount of additional memory.
The marking of visited cells with the “/” character temporarily modifies the board in-place but doesn’t significantly contribute to the space complexity.

Therefore, the overall space complexity is O(n) due to the recursive call stack.

In summary, the time complexity is \(O(m * n * 4^n)\), and the space complexity is O(n), where “m” and “n” are the dimensions of the board, and “n” is the length of the word. The time complexity is exponential in the worst case due to the depth-first search through all possible paths in the grid.

Challenging Exercises:#

Optimization Challenge: Modify the code to find all unique words that can be constructed from the grid. Instead of returning True or False, return a list of words found. Ensure that the same cell is not used more than once in constructing each word.
Board Generation: Create a function to generate random grids of characters and then use the exist method to solve them. Test the efficiency and correctness of your code by generating larger boards and words.