Leetcode 79 – Boggle Game / Word Search

The link above is to the leetcode question. This problem set can be solved using backtracking and depth first search.

The first thing to do when trying to understand these leetcode problems is to actually understand the problem and understand what it is asking you to do. So in this question, you are being asked to find out if a word is found on the game board. However, there are some restrictions.

1. The word must be constructed with sequentially adjacent cells
2. The cells may only be horizontally adjacent or vertically adjacent
3. You cannot use the same letter cell twice

So when we first think about this, we can think about the rule set. The third rule is a pretty big giveaway that we want to use a set. The set data structure allows you to only hold unique items.

The first and second rule first makes me think that we are going to be using back tracking. Why? Because it is a situation where we can think of the solution as using a state space tree. We can also apply a bounding function which would restrict the certain “nodes” that we can search for. this would be the adjacent cells. Some pseudo code could look like this:

x + 1, y
x - 1, y
x, y + 1
x, y - y

These would be our four conditions for the different directions. We would also need to check and ensure that we are not going out of bounds of the game board.

My final code solution was this:

def word_found_in_board(board: list[list[str]], word: str) -> bool:
    rows = len(board)
    columns = len(board[0])
    path = set()

    def dfs(row: str, column: str, index: int):
        if index == len(word):
            return True
        if row < 0 or column < 0 or row >= rows or column >= columns or word[index] != board[row][column] or (row, column) in path:
            return False
        
        path.add((row, column))
        result = dfs(row + 1, column, index + 1) or dfs(row - 1, column, index + 1) or dfs(row, column + 1, index + 1) or dfs(row, column - 1, index + 1)
        path.remove((row, column))
        return result
    for row in range(rows):
        for column in range(columns):
            if dfs(row, column, 0):
                return True
    return False

We get the length and width of the game board and call them “rows” and “columns”. Then we create a set called “path” which stores tuples. Each tuple is a row and column which meets the rules and requirements as stated above. Anything that meets the rules will be added to the “path” variable and then we recursively check each of the four adjacent positions.