Word Search II
We can solve the problem using Trie data structure and Depth First Search (DFS). The idea is to insert all the words into a Trie and then search the words from the given board using DFS.
Here’s the stepbystep guide to solving this problem:
Build a Trie from the given words: A Trie is a treelike data structure that is used to store a dynamic set of strings, where the keys are usually strings. We’ll insert all the given words into a Trie.
Search the Board: We’ll iterate through every cell in the given board and use DFS to check if the current cell can form any word present in the Trie.
Backtracking: As we do DFS, we’ll use backtracking to explore all possible paths from the current cell.
Python code:


Here, build_trie
function builds the Trie from the given words, and dfs
function performs the DFS to find all the words on the board. We use a set ans
to store the unique words found, and finally return it as a list.
The code handles the constraints properly and returns all words found on the board, satisfying the given conditions.
Identifying Problem Isomorphism
“Word Search II” has an approximate isomorph: “Boggle”
In “Word Search II”, you’re given a 2D board and a list of words from a dictionary. You’re required to find all words in the board. Each word must be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring and the same letter cell may not be used more than once in a word.
Similarly, in “Boggle”, you’re given a 2D grid of letters and a dictionary of words, and you need to find all valid words from the dictionary that can be formed from the letters in the grid. The rules of forming a word are the same as in “Word Search II”.
Both share a very similar structure and require a depthfirst search approach along with some form of Trie or prefix search to efficiently check if a string is a word or the prefix of a word.
The difficulty level of both problems is similar as they have the same problem structure and require similar approaches to solve.
10 Prerequisite LeetCode Problems
The “Word Search II” involves the use of DepthFirst Search (DFS) and Trie data structure. Here are 10 problems to prepare for it:
“Word Search” (LeetCode Problem #79): This problem is the simpler version where you only need to find one word instead of multiple words.
“Implement Trie (Prefix Tree)” (LeetCode Problem #208): This problem introduces the Trie data structure which is used in “Word Search II” to efficiently search for multiple words.
“Add and Search Word  Data structure design” (LeetCode Problem #211): This problem is a good next step after implementing a Trie. It challenges you to implement a data structure that supports adding and searching words.
“Prefix and Suffix Search” (LeetCode Problem #745): This problem further exercises your understanding of Trie data structures in a more complex context.
“Number of Islands” (LeetCode Problem #200): This problem helps to get comfortable with DepthFirst Search on a grid which is a crucial part for “Word Search II”.
“Flood Fill” (LeetCode Problem #733): This is another problem to practice DFS on a grid.
“Longest Word in Dictionary” (LeetCode Problem #720): In this problem, you can practice using Trie to solve realworld problems.
“Replace Words” (LeetCode Problem #648): This problem combines Trie and string manipulation, providing good practice for “Word Search II”.
“Stream of Characters” (LeetCode Problem #1032): This problem uses Trie in a streaming context, providing an interesting twist.
“Maximum XOR of Two Numbers in an Array” (LeetCode Problem #421): This problem will help you to think about how Trie can be used in a bitwise operation context.
These cover DFS and Trie, and get you comfortable with manipulating these data structures.


Problem Classification
Here is an approach to find all words from a board of characters:
Create a Trie of the words list for efficient lookup.
Do a DFS traversal of the board, exploring each valid path.
At each cell, check if prefix exists in Trie. If a full word is found, add to result.
Mark visited letters to avoid reusing in same word.
Recursively explore neighbors and backtrack.


The key is using a Trie for efficient prefix lookup to find words during DFS traversal.
Here is an implementation in Python:


The key steps are:
 Build a Trie of words
 DFS traversal of board
 Check if prefix exists in Trie
 Backtrack and mark visited
 Return all matched words
This allows efficiently finding valid words during board traversal.
Language Agnostic Coding Drills
The code provides a solution to the problem of finding all words in a given list that are also in a 2D board. The code leverages a data structure known as Trie (also known as Prefix Tree) for efficient word search, and uses DepthFirst Search (DFS) for board traversal.
Let’s break down the code into separate concepts:
Understanding the problem and data structures used: Understand how a 2D board is represented in programming and how a list of words can be searched. Also understand what a Trie data structure is and how it is used for efficient word search.
Use of defaultdict and lambda functions: Understand the use of Python’s
defaultdict
and lambda functions. Practice using these tools in different contexts, and understand how they are used here to create a Trie.Understanding of recursion and depthfirst search (DFS): The
findstr
function is a recursive function that performs DFS on the board. Understanding how DFS works, especially in the context of a 2D grid, is essential to understand this code.String manipulation: Understand how strings are created, accessed, and modified in Python. The
reduce
function is used here to traverse the Trie, which requires an understanding of string manipulation.Use of Enumerate in loops: The code uses
enumerate
in for loops to get both the index and the value of the elements. Understanding howenumerate
works and when to use it would be beneficial.Understanding Ternary Operations: The statement
[END] = word
is a Pythonic way to add a word to a Trie. Understanding this type of operation will help to understand this code.Working with sets: The result is stored in a set, which automatically removes duplicates. Understanding how to work with sets, including adding elements and converting sets to lists, is another crucial part of understanding this code.
Nested function and variable scope: The function
findstr
is defined inside the main function, and it uses variables that are defined in the outer function. Understanding how nested functions and variable scope work in Python is necessary to understand this code.
By mastering each of these smaller units of learning separately, one can combine these skills to understand the given solution. Each of these drills can be made language agnostic by focusing on the concepts (data structures, recursion, string manipulation, etc.) rather than the specific Python syntax. The final solution applies the Trie data structure for efficient word search, and uses DFS for board traversal, demonstrating a common strategy for solving complex problems in computer science: using the right data structures and algorithms for the task.
Targeted Drills in Python
Understanding the problem and data structures used: Drill: Create a 2D board and a list of words. Write a function to check if a word is present in the board.
1 2 3 4 5 6 7 8 9
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] words = ["ABCCED", "SEE", "ABCB"] def is_word_in_board(board, word): # Implementation left as an exercise
Use of defaultdict and lambda functions: Drill: Use
defaultdict
and lambda to create a dictionary with default values as empty lists.1 2
from collections import defaultdict d = defaultdict(lambda: [])
Understanding of recursion and depthfirst search (DFS): Drill: Implement a DFS to traverse a binary tree.
1 2 3 4 5 6 7 8 9 10 11 12
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def dfs(node): if node is None: return print(node.val) dfs(node.left) dfs(node.right)
String manipulation: Drill: Write a function that reverses a string.
1 2
def reverse_string(s): return s[::1]
Use of Enumerate in loops: Drill: Given a list, print each element and its index using
enumerate
.1 2 3
l = ['a', 'b', 'c', 'd', 'e'] for i, el in enumerate(l): print(f"Index: {i}, Element: {el}")
Understanding Ternary Operations: Drill: Write a function that returns the maximum of two numbers using ternary operations.
1 2
def max(a, b): return a if a > b else b
Working with sets: Drill: Create a set, add elements to it, remove duplicates from a list using a set.
1 2 3 4 5 6 7 8 9
s = set() s.add(1) s.add(2) s.add(1) print(s) l = [1, 2, 3, 2, 1] l = list(set(l)) print(l)
Nested function and variable scope: Drill: Write a function that has a nested function inside it. The nested function should modify a variable in the outer function’s scope.
1 2 3 4 5 6 7
def outer(): x = 1 def inner(): nonlocal x x += 1 inner() print(x)
Once you’ve worked through these drills, you should be equipped with the skills necessary to understand the problem and its solution. Try to combine these drills to solve the problem.