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 DepthFirst Search (DFS) to solve this problem.
Here’s a stepbystep guide to solving this problem:
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.
DepthFirst 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.
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 returnFalse
.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.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:


Example
exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED")
will returnTrue
.exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB")
will returnFalse
.
Key Takeaway
 Using DepthFirst 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 depthfirst 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 depthfirst 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:
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.
Medium Difficulty:
 130. Surrounded Regions: This problem requires a more complex application of DFS in a 2D grid.
 417. Pacific Atlantic Water Flow: This problem requires DFS traversal from multiple starting points in a 2D grid.
 529. Minesweeper: This problem involves DFS on a 2D grid. It’s slightly more complex than the “Word Search” problem.
 785. Is Graph Bipartite?: This problem requires a DFS traversal on a graph, which is a more generalized structure than a 2D grid.
 994. Rotting Oranges: This problem involves BreadthFirst Search (BFS) on a 2D grid. BFS and DFS are closely related, and understanding one could be helpful in understanding the other.
 1293. Shortest Path in a Grid with Obstacles Elimination: This problem requires BFS with state, similar to how DFS is used in the “Word Search” problem.
These cover DFS on a 2D grid, handling edge cases and state resetting in DFS/BFS.


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
Understanding of Lists and 2D Lists (Matrices)  Familiarize yourself with creation and manipulation of lists, 2D lists and their elements.
Understanding of Strings  The basics of string manipulation including indexing, slicing and reversal.
Basic Arithmetic Operations  Familiarity with basic arithmetic operations such as addition, subtraction, multiplication, and division.
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.
Control Flow  Understanding of conditional statements (
if/else
) and loops (for
).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.
Counter  Learn how to count the frequency of elements in a list or characters in a string using
Counter
from thecollections
module.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.Understanding Classes and Methods  Learn about objectoriented programming, classes, methods, and how to create instances (objects) of classes.
DepthFirst 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:
 Understanding of Lists and 2D Lists (Matrices)
 Understanding of Strings
 Basic Arithmetic Operations
 Length and Count Functions
 Control Flow
 Understanding of Dictionaries and Sets
 Counter
 Functions and Recursion
 Understanding Classes and Methods
 DepthFirst Search (DFS)
Targeted Drills in Python
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)
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])
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)
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))
Control Flow
Write a Python program that prints all even numbers between 1 and 10 using a
for
loop andif
statement.1 2 3
for i in range(1, 11): if i % 2 == 0: print(i)
Understanding of Dictionaries and Sets
Write a Python program that creates a dictionary, adds keyvalue 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())
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))
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(n1) print("Factorial of 5:", factorial(5))
Understanding Classes and Methods
Write a Python class
Person
with attributesname
andage
and a methodgreet
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()
DepthFirst 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)