Given an m x n board of characters and a list of strings words, return all words on the board.
Each word must 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 in a word.
Example 1:
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] Output: ["eat","oath"]
Example 2:
Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j] is a lowercase English letter.1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i] consists of lowercase English letters.words are unique.Problem Overview: Given an matrix of characters and a list of words, return all dictionary words that can be formed by traversing adjacent cells (up, down, left, right). Each cell can be used once per word, so the search requires controlled exploration of the grid.
Approach 1: Backtracking with HashSet (O(m*n*4^L) time, O(k*L) space)
This approach performs a depth‑first search from every cell in the grid using backtracking. As you move through neighboring cells, build the current string and check it against a HashSet of valid words. A second set containing all prefixes helps prune paths early when the partial string cannot lead to any valid word. The algorithm marks cells as visited during recursion and restores them when backtracking. Time complexity is roughly O(m*n*4^L) where L is the maximum word length, because each position can branch in four directions. Space complexity is O(k*L) for storing words and prefixes, plus recursion stack depth.
Approach 2: Backtracking with Trie (O(m*n*4^L) time, O(k*L) space)
A Trie (prefix tree) removes the need for separate prefix checks and is the standard optimized solution. Insert all words into the Trie, then start DFS from each board cell. At every step, follow the corresponding Trie child for the current character. If no child exists, terminate that search branch immediately. When a Trie node marks the end of a word, record it in the result set and continue exploring to detect longer matches. The Trie efficiently shares prefixes across words, reducing redundant comparisons and allowing multiple words to be discovered in a single traversal. The worst‑case time remains O(m*n*4^L), but practical performance improves significantly because invalid prefixes terminate early. Space complexity is O(k*L) for the Trie plus recursion stack.
Recommended for interviews: Interviewers typically expect the Trie + backtracking approach. A naive search per word shows understanding of DFS on a matrix, but the Trie demonstrates awareness of prefix optimization and scalable search across many string patterns. It reduces repeated exploration and is the solution most candidates aim for in hard grid‑search problems.
This approach uses a Trie to represent the list of words for efficient prefix matching. The algorithm performs depth-first search (DFS) on the board starting from each cell. Each path of exploration is checked against the Trie to determine if it forms any of the words or prefixes thereof. The benefit of using a Trie is that we can stop the search early if the current path does not match any prefix in the Trie, thereby improving the efficiency of the search process.
This C solution constructs a Trie for the list of words and uses a recursive DFS to explore each board cell. During the exploration, it checks for word matches and adds them to the result if found. The Trie structure is dynamically built using a set of Trie nodes. The DFS ensures not to visit the same cell multiple times within the same exploration path.
C++
Java
Python
C#
JavaScript
Time Complexity: O(M*(4*3^(L-1))), where M is the number of cells on the board, and L is the maximum length of a word.
Space Complexity: O(N*L), where N is the number of words, and L is the maximum length of a word, used by the Trie structure.
In this approach, we perform backtracking for each word individually. This avoids the overhead of constructing a Trie but involves repeated board scanning. A Recursive Depth First Search (DFS) is used to explore possibilities starting from each cell on the board. We maintain a visited matrix to ensure a letter is not reused in forming a particular word.
This C solution attempts to find each word on the board individually. We use a helper function dfs that tries to construct the word by moving to adjacent cells recursively. The solution checks for existence of a path for each word, returning as soon as one is found.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N * M * 3^L), where N is the number of words, M is the number of cells in the board, and L is the length of the word being searched in the worst case.
Space Complexity: O(L), for the recursive call stack.
| Approach | Complexity |
|---|---|
| Using Backtracking with Trie | Time Complexity: O(M*(4*3^(L-1))), where M is the number of cells on the board, and L is the maximum length of a word. |
| Using Backtracking and HashSet | Time Complexity: O(N * M * 3^L), where N is the number of words, M is the number of cells in the board, and L is the length of the word being searched in the worst case. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with HashSet | O(m*n*4^L) | O(k*L) | When implementing quickly with simple word and prefix sets |
| Backtracking with Trie | O(m*n*4^L) | O(k*L) | Best for large dictionaries and interview‑grade optimal solution |
Word Search - Backtracking - Leetcode 79 - Python • NeetCode • 380,746 views views
Watch 9 more video solutions →Practice Word Search II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor