Word Search Leetcode Problem 79 [Python Solution]

In this blog post, we will dive into the Word Search problem, specifically Word Search LeetCode Problem 79.

This is a medium difficulty problem falling under the category of Backtracking and has been featured in interviews by companies like Facebook.

We’ll explore the problem statement, constraints, and provide an efficient Python solution.

Problem Overview

The Word Search problem is quite intriguing.

We are given an m x n grid of characters or a board and a target word.

Our goal is to determine whether the given word exists in the grid.

The word can be constructed using letters from sequentially adjacent cells, where adjacency implies cells that are horizontally or vertically neighboring.

Additionally, the same letter cell cannot be used more than once.

Let’s break this down with an example:

Example 1

Input:

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

Output:

true

In this example, we can see that the word “ABCCED” can be formed by starting at the ‘A’, moving horizontally and vertically through adjacent cells to spell out the word.

Understanding Constraints

Before we delve into the solution, let’s understand the problem constraints:

• m == board.length (The number of rows)
• n == board[i].length (The number of columns)
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consist of only lowercase and uppercase English letters.

Word Search LeetCode Problem Solution

We will solve this problem using a backtracking approach, where we explore all possible paths starting from each cell in the grid to find the target word.

If we find a valid path, we return true, indicating that the word can be formed.

Otherwise, we return false.

1. Bruteforce Approach

Our backtracking function will consider the following conditions:

1. If we have reached the end of the word, we return True.
2. If we are out of bounds (i.e., row or column is less than 0 or greater than or equal to the dimensions of the board), we return False.
3. If the character in the grid at the current position does not match the character we are looking for, we return False.
4. If we have already visited the current position in our path, we return False.

If none of the above conditions are met, we continue exploring by moving to neighboring cells (up, down, left, and right) recursively.

If any of these recursive calls return True, we propagate it up and return True.

def exist(board, word):
    ROWS, COLS = len(board), len(board[0])
    path = set()

    def dfs(r, c, i):
        if i == len(word):
            return True
        if (
            min(r, c) < 0
            or r >= ROWS
            or c >= COLS
            or word[i] != board[r][c]
            or (r, c) in path
        ):
            return False
        path.add((r, c))
        res = (
            dfs(r + 1, c, i + 1)
            or dfs(r - 1, c, i + 1)
            or dfs(r, c + 1, i + 1)
            or dfs(r, c - 1, i + 1)
        )
        path.remove((r, c))
        return res

    count = defaultdict(int, sum(map(Counter, board), Counter()))
    if count[word[0]] > count[word[-1]]:
        word = word[::-1]

    for r in range(ROWS):
        for c in range(COLS):
            if dfs(r, c, 0):
                return True
    return False

Time and Space Complexity

The time complexity of this solution is roughly O(n * m * 4^n), where n and m are the dimensions of the board, and 4^n represents the number of recursive calls in the worst case.

The space complexity is O(n), which accounts for the space used by the path set during the backtracking process.

Reasoning Behind Our Approach

The backtracking approach allows us to explore all possible paths in the grid.

By adhering to the problem constraints and conditions, we can efficiently determine whether the target word can be formed.

The use of a path set helps us avoid revisiting the same position during exploration, ensuring the correct result.

In this solution, we also optimize the word reversal to prevent a Time Limit Exceeded (TLE) error.

This is done by checking the frequency of the first and last characters in the word and reversing it if needed.

Related Interview Questions By Company:

• Best Time To Buy And Sell Stock II LeetCode
• Ones And Zeroes LeetCode
• Asteroid Collision LeetCode

Related Interview Questions By Difficulty:

• Combinations LeetCode
• Permutations LeetCode
• Find Unique Binary String LeetCode

Conclusion

In conclusion, the Word Search problem is a challenging puzzle that involves backtracking through a grid to find a target word.

While the approach is not the most efficient, it provides a thorough exploration of all possibilities and ensures that the word can be found in the grid.

You can find the full problem description and try it yourself on LeetCode.

We hope this blog post has helped you understand the problem and provided a clear, beginner-friendly Python solution.

If you have any questions or suggestions, feel free to comment and share your thoughts.

Happy coding!