# 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.