Word Search

The problem asks us to determine whether a given word can be constructed from a grid of characters, where we can move horizontally or vertically, and we can’t use the same cell more than once. We can use Depth-First Search (DFS) to solve this problem.

Here’s a step-by-step guide to solving this problem:

  1. Iterate through the Grid: Start by iterating through each cell of the grid. If a cell has the same character as the first character of the word, we’ll begin our DFS search from that cell.

  2. Depth-First Search (DFS): We’ll define a recursive function that explores the current cell’s neighbors (up, down, left, right) if they match the next character in the word. We’ll keep track of the visited cells by either marking them in place or using a separate visited structure.

  3. Base Cases: If the current index of the word we are looking for matches the length of the word, we’ve found the word, and we return True. If we go out of bounds or find a mismatched character, we return False.

  4. Recursive Cases: For each neighbor that matches the next character in the word, we’ll call the DFS function recursively, marking the current cell as visited. If any of the recursive calls return True, we’ve found the word.

  5. Clean Up: After visiting the neighbors, we’ll need to unmark the current cell so that it can be used in a different path.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(x, y, index):
            if index == len(word):
                return True
            if x < 0 or y < 0 or x >= m or y >= n or board[x][y] != word[index]:
                return False

            # Mark the cell as visited
            board[x][y] = '#'
            found = dfs(x + 1, y, index + 1) or \
                   dfs(x - 1, y, index + 1) or \
                   dfs(x, y + 1, index + 1) or \
                   dfs(x, y - 1, index + 1)

            # Unmark the cell
            board[x][y] = word[index]
            return found

        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0] and dfs(i, j, 0):
                    return True
        return False

Example

  • exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED") will return True.
  • exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB") will return False.

Key Takeaway

  • Using Depth-First Search (DFS), we can explore all possible paths from each cell of the grid, effectively searching for the word. The marking and unmarking of the cells ensure that we don’t revisit them in the same path.

Identifying Problem Isomorphism

“Word Search” has an approximate isomorph: “Rat in a Maze”

In “Word Search”, you’re given a 2D board and a word. You’re required to check if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where “adjacent” cells are those horizontally or vertically neighboring and the same cell may not be used more than once.

Similarly, in “Rat in a Maze”, you’re given a 2D grid representing a maze and you need to find if there is a path from the top left corner to the bottom right corner. The rat can move in four directions: up, down, left, and right. But it cannot revisit a cell, similar to how a cell cannot be used more than once in “Word Search”.

Both involve exploring a grid with constraints on movement and revisitation. They require a depth-first search or backtracking approach to explore all possibilities and to determine if the target can be reached or not.

“Rat in a Maze” is simpler than the “Word Search” because it only requires finding a path from one point to another, whereas the other involves checking if a specific sequence (word) exists in the grid.

10 Prerequisite LeetCode Problems

“Word Search” is a classic application of depth-first search (DFS) on a 2D grid. It also involves handling of edge cases and state resetting. Here are 10 problems to prepare for this problem:

  1. Easy Difficulty:

    • 200. Number of Islands: This problem also requires DFS traversal in a 2D grid, similar to the “Word Search” problem.
    • 463. Island Perimeter: This problem requires traversal in a 2D grid to calculate perimeter of islands.
    • 733. Flood Fill: This problem also requires DFS in a 2D grid. It’s easier than the “Word Search” problem and can help in understanding the DFS approach on a 2D grid.
    • 766. Toeplitz Matrix: This problem requires checking diagonals in a 2D grid.

  2. Medium Difficulty:

These cover DFS on a 2D grid, handling edge cases and state resetting in DFS/BFS.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        R = len(board)
        C = len(board[0])

        if len(word) > R*C:
            return False

        count = Counter(sum(board, []))
        
        for c, countWord in Counter(word).items():
            if count[c] < countWord:
                return False

        if count[word[0]] > count[word[-1]]:
             word = word[::-1]

        seen = set()

        def dfs(r, c, i):
            if i == len(word):
                return True
            if r < 0 or c < 0 or r >= R or c >= C or word[i] != board[r][c] or (r,c) in seen:
                return False

            seen.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) 
            )
            seen.remove((r,c))  #backtracking

            return res

        for i in range(R):
            for j in range(C):
                if dfs(i,j,0):
                    return True
        return False

Problem Classification

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED” Output: true

Example 2:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE” Output: true

Example 3:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB” Output: false

Constraints:

m == board.length n = board[i].length 1 <= m, n <= 6 1 <= word.length <= 15 board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Language Agnostic Coding Drills

  1. Understanding of Lists and 2D Lists (Matrices) - Familiarize yourself with creation and manipulation of lists, 2D lists and their elements.

  2. Understanding of Strings - The basics of string manipulation including indexing, slicing and reversal.

  3. Basic Arithmetic Operations - Familiarity with basic arithmetic operations such as addition, subtraction, multiplication, and division.

  4. Length and Count Functions - Learn how to use length and count functions to get the size of a list or string, and count the occurrences of elements.

  5. Control Flow - Understanding of conditional statements (if/else) and loops (for).

  6. Understanding of Dictionaries and Sets - Learn how to create and manipulate dictionaries and sets. Understanding how to add and remove elements, and the concept of keys and values in dictionaries.

  7. Counter - Learn how to count the frequency of elements in a list or characters in a string using Counter from the collections module.

  8. Functions and Recursion - Understand how to define functions and the concept of recursion. In this case, the function dfs is recursive as it calls itself.

  9. Understanding Classes and Methods - Learn about object-oriented programming, classes, methods, and how to create instances (objects) of classes.

  10. Depth-First Search (DFS) - DFS is a common algorithm used in graph theory. This code is using a modified version of DFS to find a path in a 2D grid.

Arranged in order of increasing difficulty, the learning units would look something like this:

  1. Understanding of Lists and 2D Lists (Matrices)
  2. Understanding of Strings
  3. Basic Arithmetic Operations
  4. Length and Count Functions
  5. Control Flow
  6. Understanding of Dictionaries and Sets
  7. Counter
  8. Functions and Recursion
  9. Understanding Classes and Methods
  10. Depth-First Search (DFS)

Targeted Drills in Python

  1. Understanding of Lists and 2D Lists (Matrices)

    Write a Python program that creates a list, adds elements to it, prints its length, accesses individual elements, and prints the whole list. Repeat the same process for a 2D list.

    1
2
3
4

    list_1d = [1, 2, 3, 4, 5]
print("Length of list:", len(list_1d))
print("Element at index 2:", list_1d[2])
print("Full List:", list_1d)

  2. Understanding of Strings

    Write a Python program that creates a string, prints its length, accesses individual characters, slices it, and reverses it.

    1
2
3
4
5

    string = "Hello, world!"
print("Length of string:", len(string))
print("Character at index 5:", string[5])
print("Slice from index 2 to 5:", string[2:5])
print("Reversed string:", string[::-1])

  3. Basic Arithmetic Operations

    Write a Python program that performs basic arithmetic operations (addition, subtraction, multiplication, and division).

    1
2
3
4
5

    num1, num2 = 10, 3
print("Addition:", num1 + num2)
print("Subtraction:", num1 - num2)
print("Multiplication:", num1 * num2)
print("Division:", num1 / num2)

  4. Length and Count Functions

    Write a Python program that counts the number of occurrences of a specific element in a list.

    1
2

    list_1d = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
print("Number of occurrences of 2:", list_1d.count(2))

  5. Control Flow

    Write a Python program that prints all even numbers between 1 and 10 using a for loop and if statement.

    1
2
3

    for i in range(1, 11):
    if i % 2 == 0:
        print(i)

  6. Understanding of Dictionaries and Sets

    Write a Python program that creates a dictionary, adds key-value pairs to it, prints the whole dictionary, accesses individual values using keys, and prints all keys and values. Do the same for a set.

    1
2
3
4
5

    dictionary = {"apple": "red", "banana": "yellow", "grape": "purple"}
print("Full Dictionary:", dictionary)
print("Value of key 'apple':", dictionary["apple"])
print("All keys:", dictionary.keys())
print("All values:", dictionary.values())

  7. Counter

    Write a Python program that counts the frequency of each character in a string using Counter.

    1
2
3

    from collections import Counter
string = "Hello, world!"
print("Character frequencies:", Counter(string))

  8. Functions and Recursion

    Write a Python function that calculates the factorial of a number using recursion.

    1
2
3
4
5
6

    def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
print("Factorial of 5:", factorial(5))

  9. Understanding Classes and Methods

    Write a Python class Person with attributes name and age and a method greet that prints a greeting message.

    1
2
3
4
5
6
7
8
9

    class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    def greet(self):
        print(f"Hello, my name is {self.name} and I am {self.age} years old.")

person1 = Person("Alice", 25)
person1.greet()

  10. Depth-First Search (DFS)

    Implement a Python function that performs DFS on a graph represented as an adjacency list.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    graph = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}
visited = set()

def dfs(node):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbor in graph[node]:
            dfs(neighbor)

dfs(1)