5 Best Ways to Check If a Word Exists in a Grid or Not in Python

Rate this post

πŸ’‘ Problem Formulation: Imagine you have a 2D grid of letters, reminiscent of a word search puzzle, and you need to determine if a particular word can be found within this grid. This may involve checking horizontal, vertical, or diagonal lines in the grid. Given a grid, such as [["a","b","c"],["d","e","f"],["g","h","i"]], and a word, like “bed”, the task is to write a Python function that returns True if the word exists or False otherwise.

Method 1: Horizontal Search

In a horizontal search, we loop through each row of the grid and check if the word can be formed by concatenating characters. One common way to implement this is to join each row into a string and check for the word using Python’s in keyword.

Here’s an example:

def horizontal_search(grid, word):
    for row in grid:
        if word in "".join(row):
            return True
    return False

grid = [["a","b","c"],["d","e","f"],["g","h","i"]]
word = "bed"
print(horizontal_search(grid, word))

Output:

False

This code snippet defines a function that iterates over each row in the grid, joining the characters, and checks if the word is present. In the provided grid, “bed” does not appear horizontally, so the function returns False.

Method 2: Vertical Search

Vertical search involves checking every column for the presence of the word. This can be done by transposing the grid and performing a similar operation as the horizontal search. Transposition can be achieved using list comprehension and Python’s zip function.

Here’s an example:

def vertical_search(grid, word):
    transposed = zip(*grid)
    return any(word in "".join(col) for col in transposed)

grid = [["a","b","c"],["d","e","f"],["g","h","i"]]
word = "cfi"
print(vertical_search(grid, word))

Output:

True

This code snippet transposes the grid and checks each column for the word. Function vertical_search finds the word “cfi” vertically in the grid, thus it returns True.

Method 3: Diagonal Search

Diagonal search checks for the word in both diagonals of the grid. This requires constructing strings from the diagonals of the grid and applying the word search there. Due to the complexity of diagonals, this method can be a bit more intricate than horizontal and vertical searches.

Here’s an example:

def diagonal_search(grid, word):
    n, m = len(grid), len(grid[0])
    diagonals = [''.join(grid[i+k][k] for k in range(min(n-i, m))) for i in range(n)]
    diagonals += [''.join(grid[k][i+k] for k in range(min(m-i, n))) for i in range(1, m)]
    return any(word in d for d in diagonals)

grid = [["a","b","c"],["d","e","f"],["g","h","i"]]
word = "aei"
print(diagonal_search(grid, word))

Output:

True

The given function diagonal_search extracts all diagonals from the grid and checks each one for the presence of the word. As “aei” is on a diagonal in the grid, the function outputs True.

Method 4: Depth-First Search (DFS)

Depth-first search (DFS) is a more universal way to search the grid. It traverses the grid recursively, attempting to build the word from each position. It can detect words in horizontal, vertical, and diagonal directions, and even backtrack if the current path doesn’t yield the word.

Here’s an example:

def exist(board, word):
    def dfs(index, x, y):
        if index == len(word):
            return True
        if x < 0 or y < 0 or x == len(board) or y == len(board[0]) or board[x][y] != word[index]:
            return False
        tmp, board[x][y] = board[x][y], '/'
        res = (dfs(index+1, x+1, y) or dfs(index+1, x, y+1) or
               dfs(index+1, x-1, y) or dfs(index+1, x, y-1))
        board[x][y] = tmp
        return res
    
    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(0, i, j):
                return True
    return False

board = [["a","b","c"],["d","e","f"],["g","h","i"]]
word = "cfi"
print(exist(board, word))

Output:

True

This code snippet implements a DFS algorithm that starts from each cell and tries to build the word character by character in all four directions. It marks cells as visited by temporarily changing the value. As the search for “cfi” is successful, it returns True.

Bonus One-Liner Method 5: Compact DFS

This bonus method offers a compact version of the DFS approach, utilizing lambda functions and list comprehensions. It’s a condensed form of the previous method but equivalent in functionality and efficiency.

Here’s an example:

exist = lambda b, w: any(dfs(w, b, i, j, {(i, j)}) for i in range(len(b)) for j in range(len(b[0])))
dfs = lambda w, b, x, y, v: w == "" or ((x, y) not in v and any(dfs(w[1:], b, X, Y, v | {(x, y)}) for X, Y in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)) if 0 <= X < len(b) and 0 <= Y < len(b[0]) and b[X][Y] == w[0]))

board = [["a","b","c"],["d","e","f"],["g","h","i"]]
word = "cfi"
print(exist(board, word))

Output:

True

This one-liner defines two lambda functions: exist, which iterates over the grid, and dfs, which performs the depth-first search. The compact syntax may be elegant, but readability is significantly hampered. Despite this, it correctly identifies “cfi” in the grid.

Summary/Discussion

  • Method 1: Horizontal Search. This is quick and simple, best for unidirectional searches. Limited to horizontal word checking.
  • Method 2: Vertical Search. Similar to the horizontal search but checks columns, can be combined with horizontal search for better coverage. Ignores diagonal possibilities.
  • Method 3: Diagonal Search. It complements horizontal and vertical methods to cover all straight-line possibilities within the grid. More complex and less efficient than the first two methods.
  • Method 4: Depth-First Search (DFS). Versatile and covers all search directions, best for thorough searches. More resource-intensive and can be overkill for simple patterns.
  • Bonus Method 5: Compact DFS. All the perks of DFS in a concise format. Not easily understandable, better for experienced coders looking for a compact solution.