Solving "Word Search" problem

Recently, I attempted to solve "Word Search" leetcode

"Word Search" is a game that the objective is to find a specific word (or even multiple words).

In this post I'll explain in detail how to tackle this problem.

Take a look at this image showing the word "LIFE" in a grid:

How do we solve this problem? How can we write code to search for this word efficiently?

Reasoning

Before delving into complex topics like graphs, depth-first search (DFS), and backtracking, let's consider how we solve word searches in real life.

Initially, we try to locate the first letter of the word, quickly scanning all the letters. Then, we follow the subsequent letters to see if they form the word, checking in all directions but only one at a time.
Then, we follow the next letters in order to check if we find the word. But in which direction? All of them, but one at a time.

In short:

• Locate the first letter (L in this case);
• Attempt to find the word by following all the letters to the right;
• If we don't find, we try all the letters below, and so on.

With this approach in mind, we can move on to the next part.

Writing the algorithm

Let's describe the algorithm in simple terms to clarify our thoughts, almost as if talking about them out loud.

Here are the steps:

• Iterate the grid (each row and column);
• If grid[row][col] matches the first letter of our word, start searching for the remaining letters from there;
• Use depth-first search algorithm;
• In each DFS call, check if the current letter is the next one in the word;
• If not, return False;
• If it matches, continue searching for the other letters;
• When the word is found, return True.

Here is the Python code to solve it:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(row, col, index):
            if len(word) == index:
                return True

            # check if we don't surpass the grid
            row_outbounds = row < 0 or row >= len(board)
            col_outbounds = col < 0 or col >= len(board[0])

            if row_outbounds or col_outbounds:
                return False

            wrong_letter = board[row][col] != word[index]

            if wrong_letter:
                return False

            letter = board[row][col]
            # mark visited
            board[row][col] = "#"

            # dfs in all directions
            if (dfs(row - 1, col, index + 1) or 
                dfs(row, col + 1, index + 1) or 
                dfs(row + 1, col, index + 1) or 
                dfs(row, col - 1, index + 1)):
                return True

            # not found, unmark
            board[row][col] = letter
            return False


        # iterate over the grid
        for row in range(len(board)):
            for col in range(len(board[0])):
                if board[row][col] == word[0]:
                    if dfs(row, col, 0):
                        return True

        return False

Let's dive deeper into the code.

This code iterates over the grid, and when it finds the first letter of the word, it starts a search for the subsequent letters. The index parameter plays a crucial role, as explained below.

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

return False

dfs is our recursive function used to traverse the grid in search of the next letters of the word. We increment index each time we find a matching letter. For instance, if we find the letter "L," it corresponds to index zero in the array ["L", "I", "F", "E"].

def dfs(row, col, index):
    if len(word) == index:
        return True

    # check if we don't surpass the grid
    row_outbounds = row < 0 or row >= len(board)
    col_outbounds = col < 0 or col >= len(board[0])

    if row_outbounds or col_outbounds:
        return False

    wrong_letter = board[row][col] != word[index]

    if wrong_letter:
        return False

This code also ensures we avoid 'out of range' errors:

row_outbounds = row < 0 or row >= len(board)
col_outbounds = col < 0 or col >= len(board[0])

And here, we check if the current letter is correct:

wrong_letter = board[row][col] != word[index]
if wrong_letter:
    return False

Here is what I find to be the most challenging aspect of this solution: traversing the board recursively.

We save each letter because we need to mark its row and column as visited. Why is this important? It prevents the algorithm from retraversing the same path. In the code, we accomplish this by setting an arbitrary character (in this case, "#") at the position. After exploring all possible paths from this position, we 'unmark' the cell by restoring the saved letter. This step is crucial because it returns the board to its original state, allowing subsequent calls of the dfs function to use this letter for other potential paths.

letter = board[row][col]
# mark visited
board[row][col] = "#"

# dfs in all directions
if (dfs(row - 1, col, index + 1) or 
    dfs(row, col + 1, index + 1) or 
    dfs(row + 1, col, index + 1) or 
    dfs(row, col - 1, index + 1)):
    return True

# not found, unmark
board[row][col] = letter

return False

Additionally, it's important to note that we execute the dfs function four times, each call moving in a different direction (up, right, down, left).

Time and space complexity

Understanding the time and space complexity is essential to evaluate the performance of your solution.

Measuring time complexity of "Word Search" is not an easy task. We can describe it as O(R * C * 4 ^ L) where:

• R = number of rows in the grid;
• C = number of columns in the grid;
• 4 = reflects the four directions (up, down, right, left) from each cell;
• L = length of the word.

We can simplify it to O(N ^ 2 * 4 ^ L) where N is the larger of the number of rows or columns in the grid (thank you @viglioni )

As you can see, it is not so efficient.

Space complexity of the solution is O(L) because L is the max recursion depth we need to explore all the possibilies before finding the word (or unwinding the stack when it does encounter a wrong letter).

Conclusion

In this article, we explored a detailed solution to the "Word Search" problem, employing a depth-first search (DFS) approach. By breaking down the problem into manageable steps and translating these into Python code, we've demonstrated a practical application of graph traversal algorithms in solving complex problems.