Language Selection
Choose your preferred programming language
Showing: Python
Word Search II
Problem Statement
You are given an m x n grid board of lowercase letters and a list of distinct strings words. Return every word from the list that can be spelled on the board.
A word is spelled by starting at any cell and repeatedly stepping to a horizontally or vertically adjacent cell, reading one letter per cell. A single cell may be used at most once within the same word. The result may be returned in any order.
Examples
Example 1:
Input:
board = [["c","a","t"],
["r","o","e"],
["b","a","d"]]
words = ["cat","road","bad","toe","coat"]
Output: ["cat","road","bad"]
Explanation:
"cat" runs along the top row, "bad" along the bottom row, and "road" goes
r(1,0) -> o(1,1) -> a(2,1) -> d(2,2). "toe" fails because "o" is only diagonal
to "t", and "coat" fails because "c" has no neighbouring "o".
Example 2:
Input:
board = [["a","b"],
["c","d"]]
words = ["abdc","abc","acdb","bd"]
Output: ["abdc","acdb","bd"]
Explanation: "abc" would need "b" and "c" to be adjacent, but they are diagonal.
Example 3:
Input: board = [["z"]], words = ["zz","z"]
Output: ["z"]
Explanation: "zz" would have to use the single cell twice.
Constraints
1 <= m, n <= 12board[i][j]is a lowercase English letter1 <= words.length <= 3 * 10^41 <= words[i].length <= 10words[i]consists of lowercase English letters, and all words are distinct
Approach 1: Backtracking Search for Each Word
Algorithm
Solve Word Search once per word: for each word, try every cell as a starting point and backtrack through neighbours.
- For each word, for each cell
(r, c), rundfs(r, c, i), meaning “canword[i:]be spelled starting at(r, c)?” - In
dfs, fail if the cell’s letter differs fromword[i]. Succeed ifiis the last index. - Otherwise mark the cell as used (overwrite it with
'#'), try the four neighbours withi + 1, then restore the letter. - Add the word to the result if any start cell succeeds.
This is correct, but words that share a prefix repeat the same exploration, and every word re-scans the whole board.
Implementation
Python:
from typing import List
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
rows, cols = len(board), len(board[0])
def dfs(word, r, c, i):
if board[r][c] != word[i]:
return False
if i == len(word) - 1:
return True
board[r][c] = '#' # mark as used on the current path
found = False
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and dfs(word, nr, nc, i + 1):
found = True
break
board[r][c] = word[i] # restore before returning
return found
result = []
for word in words:
if any(dfs(word, r, c, 0) for r in range(rows) for c in range(cols)):
result.append(word)
return result
Java:
import java.util.ArrayList;
import java.util.List;
class Solution {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<>();
for (String word : words) {
if (exists(board, word)) result.add(word);
}
return result;
}
private boolean exists(char[][] board, String word) {
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
if (dfs(board, word, r, c, 0)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, int r, int c, int i) {
if (board[r][c] != word.charAt(i)) return false;
if (i == word.length() - 1) return true;
char saved = board[r][c];
board[r][c] = '#'; // mark as used on the current path
boolean found = false;
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length
&& dfs(board, word, nr, nc, i + 1)) {
found = true;
break;
}
}
board[r][c] = saved; // restore before returning
return found;
}
}
Go:
func findWords(board [][]byte, words []string) []string {
rows, cols := len(board), len(board[0])
dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var dfs func(word string, r, c, i int) bool
dfs = func(word string, r, c, i int) bool {
if board[r][c] != word[i] {
return false
}
if i == len(word)-1 {
return true
}
board[r][c] = '#' // mark as used on the current path
found := false
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && dfs(word, nr, nc, i+1) {
found = true
break
}
}
board[r][c] = word[i] // restore before returning
return found
}
result := []string{}
for _, word := range words {
search:
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if dfs(word, r, c, 0) {
result = append(result, word)
break search
}
}
}
}
return result
}
JavaScript:
/**
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
var findWords = function(board, words) {
const rows = board.length, cols = board[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const dfs = (word, r, c, i) => {
if (board[r][c] !== word[i]) return false;
if (i === word.length - 1) return true;
board[r][c] = '#'; // mark as used on the current path
let found = false;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dfs(word, nr, nc, i + 1)) {
found = true;
break;
}
}
board[r][c] = word[i]; // restore before returning
return found;
};
const exists = (word) => {
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(word, r, c, 0)) return true;
}
}
return false;
};
return words.filter(exists);
};
C#:
using System.Collections.Generic;
public class Solution {
private static readonly int[][] Dirs = { new[] { 1, 0 }, new[] { -1, 0 }, new[] { 0, 1 }, new[] { 0, -1 } };
public IList<string> FindWords(char[][] board, string[] words) {
var result = new List<string>();
foreach (string word in words) {
if (Exists(board, word)) result.Add(word);
}
return result;
}
private static bool Exists(char[][] board, string word) {
for (int r = 0; r < board.Length; r++) {
for (int c = 0; c < board[0].Length; c++) {
if (Dfs(board, word, r, c, 0)) return true;
}
}
return false;
}
private static bool Dfs(char[][] board, string word, int r, int c, int i) {
if (board[r][c] != word[i]) return false;
if (i == word.Length - 1) return true;
char saved = board[r][c];
board[r][c] = '#'; // mark as used on the current path
bool found = false;
foreach (int[] d in Dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < board.Length && nc >= 0 && nc < board[0].Length
&& Dfs(board, word, nr, nc, i + 1)) {
found = true;
break;
}
}
board[r][c] = saved; // restore before returning
return found;
}
}
C++:
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> result;
for (const string& word : words) {
if (exists(board, word)) result.push_back(word);
}
return result;
}
private:
bool exists(vector<vector<char>>& board, const string& word) {
for (int r = 0; r < (int)board.size(); r++) {
for (int c = 0; c < (int)board[0].size(); c++) {
if (dfs(board, word, r, c, 0)) return true;
}
}
return false;
}
bool dfs(vector<vector<char>>& board, const string& word, int r, int c, size_t i) {
if (board[r][c] != word[i]) return false;
if (i == word.size() - 1) return true;
const int dr[4] = {1, -1, 0, 0};
const int dc[4] = {0, 0, 1, -1};
char saved = board[r][c];
board[r][c] = '#'; // mark as used on the current path
bool found = false;
for (int d = 0; d < 4 && !found; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < (int)board.size() && nc >= 0 && nc < (int)board[0].size()) {
found = dfs(board, word, nr, nc, i + 1);
}
}
board[r][c] = saved; // restore before returning
return found;
}
};
Complexity Analysis
- Time: O(W * m * n * 4 * 3^(L-1)) for
Wwords of length at mostL. Each search can start at any of them * ncells; the first step has 4 directions and every later step at most 3 (it cannot go back to the cell it came from). - Space: O(L) for the recursion depth (the board is marked in place). The result list is not counted.
Approach 2: Trie + Single Backtracking Pass with Pruning (Optimal)
Algorithm
Instead of searching for each word separately, put all words in a trie and walk the board and the trie together. A DFS path on the board is only continued while the letters read so far are a prefix of some word, so every word sharing that prefix is explored at once.
- Build the trie. Insert each word; on the node for its last letter, store the word itself (instead of a boolean), so a match can be reported without rebuilding the string.
- Start a DFS from every cell with the trie root as the parent node.
- In
dfs(r, c, parent):- Look up the child of
parentforboard[r][c]. If there is none, no word continues this way: return. - If that child stores a word, add it to the result and clear it, so the same word is not reported twice.
- Mark the cell with
'#', recurse into the four neighbours with the child as the new parent, then restore the letter. - Prune: if the child now has no children and no word left, remove it from
parent. Future searches will stop one step earlier, and once every word is found the root becomes empty and the remaining DFS calls return immediately.
- Look up the child of
The DFS depth is at most the longest word (10), so recursion is safe.
Implementation
Python:
from typing import List
class TrieNode:
__slots__ = ("children", "word")
def __init__(self):
self.children = {} # char -> TrieNode
self.word = None # the full word if one ends at this node
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for w in words:
node = root
for ch in w:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.word = w
rows, cols = len(board), len(board[0])
found = []
def dfs(r, c, parent):
ch = board[r][c]
node = parent.children.get(ch) # '#' (used cell) is never a child
if node is None:
return
if node.word is not None:
found.append(node.word)
node.word = None # report each word only once
board[r][c] = '#' # mark as used on the current path
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols:
dfs(nr, nc, node)
board[r][c] = ch # restore before returning
# Prune a branch that can no longer produce any word
if not node.children and node.word is None:
del parent.children[ch]
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return found
Java:
import java.util.ArrayList;
import java.util.List;
class Solution {
private static class TrieNode {
final TrieNode[] children = new TrieNode[26];
int childCount; // number of non-null children, for O(1) pruning checks
String word; // the full word if one ends at this node
}
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private char[][] board;
private List<String> found;
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode node = root;
for (int i = 0; i < w.length(); i++) {
int c = w.charAt(i) - 'a';
if (node.children[c] == null) {
node.children[c] = new TrieNode();
node.childCount++;
}
node = node.children[c];
}
node.word = w;
}
this.board = board;
this.found = new ArrayList<>();
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
dfs(r, c, root);
}
}
return found;
}
private void dfs(int r, int c, TrieNode parent) {
char ch = board[r][c];
if (ch == '#') return; // already on the current path
TrieNode node = parent.children[ch - 'a'];
if (node == null) return;
if (node.word != null) {
found.add(node.word);
node.word = null; // report each word only once
}
board[r][c] = '#'; // mark as used on the current path
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length) {
dfs(nr, nc, node);
}
}
board[r][c] = ch; // restore before returning
// Prune a branch that can no longer produce any word
if (node.childCount == 0 && node.word == null) {
parent.children[ch - 'a'] = null;
parent.childCount--;
}
}
}
Go:
type trieNode struct {
children [26]*trieNode
childCount int // number of non-nil children, for O(1) pruning checks
word string // the full word if one ends at this node ("" otherwise)
}
func findWords(board [][]byte, words []string) []string {
root := &trieNode{}
for _, w := range words {
node := root
for i := 0; i < len(w); i++ {
c := w[i] - 'a'
if node.children[c] == nil {
node.children[c] = &trieNode{}
node.childCount++
}
node = node.children[c]
}
node.word = w // words have length >= 1, so "" safely means "no word"
}
rows, cols := len(board), len(board[0])
dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
found := []string{}
var dfs func(r, c int, parent *trieNode)
dfs = func(r, c int, parent *trieNode) {
ch := board[r][c]
if ch == '#' { // already on the current path
return
}
node := parent.children[ch-'a']
if node == nil {
return
}
if node.word != "" {
found = append(found, node.word)
node.word = "" // report each word only once
}
board[r][c] = '#' // mark as used on the current path
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
dfs(nr, nc, node)
}
}
board[r][c] = ch // restore before returning
// Prune a branch that can no longer produce any word
if node.childCount == 0 && node.word == "" {
parent.children[ch-'a'] = nil
parent.childCount--
}
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
dfs(r, c, root)
}
}
return found
}
JavaScript:
/**
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
var findWords = function(board, words) {
// Trie node: { children: Map<char, node>, word: string | null }
const root = { children: new Map(), word: null };
for (const w of words) {
let node = root;
for (const ch of w) {
if (!node.children.has(ch)) {
node.children.set(ch, { children: new Map(), word: null });
}
node = node.children.get(ch);
}
node.word = w;
}
const rows = board.length, cols = board[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const found = [];
const dfs = (r, c, parent) => {
const ch = board[r][c];
const node = parent.children.get(ch); // '#' (used cell) is never a child
if (node === undefined) return;
if (node.word !== null) {
found.push(node.word);
node.word = null; // report each word only once
}
board[r][c] = '#'; // mark as used on the current path
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
dfs(nr, nc, node);
}
}
board[r][c] = ch; // restore before returning
// Prune a branch that can no longer produce any word
if (node.children.size === 0 && node.word === null) {
parent.children.delete(ch);
}
};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
dfs(r, c, root);
}
}
return found;
};
C#:
using System.Collections.Generic;
public class Solution {
private class TrieNode {
public readonly TrieNode[] Children = new TrieNode[26];
public int ChildCount; // number of non-null children, for O(1) pruning checks
public string Word; // the full word if one ends at this node
}
private static readonly int[] Dr = { 1, -1, 0, 0 };
private static readonly int[] Dc = { 0, 0, 1, -1 };
private char[][] board;
private List<string> found;
public IList<string> FindWords(char[][] board, string[] words) {
var root = new TrieNode();
foreach (string w in words) {
TrieNode node = root;
foreach (char ch in w) {
int c = ch - 'a';
if (node.Children[c] == null) {
node.Children[c] = new TrieNode();
node.ChildCount++;
}
node = node.Children[c];
}
node.Word = w;
}
this.board = board;
this.found = new List<string>();
for (int r = 0; r < board.Length; r++) {
for (int c = 0; c < board[0].Length; c++) {
Dfs(r, c, root);
}
}
return found;
}
private void Dfs(int r, int c, TrieNode parent) {
char ch = board[r][c];
if (ch == '#') return; // already on the current path
TrieNode node = parent.Children[ch - 'a'];
if (node == null) return;
if (node.Word != null) {
found.Add(node.Word);
node.Word = null; // report each word only once
}
board[r][c] = '#'; // mark as used on the current path
for (int d = 0; d < 4; d++) {
int nr = r + Dr[d], nc = c + Dc[d];
if (nr >= 0 && nr < board.Length && nc >= 0 && nc < board[0].Length) {
Dfs(nr, nc, node);
}
}
board[r][c] = ch; // restore before returning
// Prune a branch that can no longer produce any word
if (node.ChildCount == 0 && node.Word == null) {
parent.Children[ch - 'a'] = null;
parent.ChildCount--;
}
}
}
C++:
#include <memory>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
auto root = make_unique<TrieNode>();
for (const string& w : words) {
TrieNode* node = root.get();
for (char ch : w) {
int c = ch - 'a';
if (!node->children[c]) {
node->children[c] = make_unique<TrieNode>();
node->childCount++;
}
node = node->children[c].get();
}
node->word = &w;
}
vector<string> found;
for (int r = 0; r < (int)board.size(); r++) {
for (int c = 0; c < (int)board[0].size(); c++) {
dfs(board, r, c, root.get(), found);
}
}
return found;
}
private:
struct TrieNode {
unique_ptr<TrieNode> children[26];
int childCount = 0; // number of non-null children, for O(1) pruning checks
const string* word = nullptr; // points at the word ending here, if any
};
void dfs(vector<vector<char>>& board, int r, int c, TrieNode* parent, vector<string>& found) {
char ch = board[r][c];
if (ch == '#') return; // already on the current path
TrieNode* node = parent->children[ch - 'a'].get();
if (!node) return;
if (node->word) {
found.push_back(*node->word);
node->word = nullptr; // report each word only once
}
board[r][c] = '#'; // mark as used on the current path
const int dr[4] = {1, -1, 0, 0};
const int dc[4] = {0, 0, 1, -1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < (int)board.size() && nc >= 0 && nc < (int)board[0].size()) {
dfs(board, nr, nc, node, found);
}
}
board[r][c] = ch; // restore before returning
// Prune a branch that can no longer produce any word (frees the node)
if (node->childCount == 0 && !node->word) {
parent->children[ch - 'a'].reset();
parent->childCount--;
}
}
};
Complexity Analysis
- Time: O(m * n * 4 * 3^(L-1)) for the board search, where
Lis the maximum word length, plus O(T) to build the trie, whereTis the total number of characters inwords. Each DFS follows trie edges, so a path never gets longer thanLno matter how many words there are; that removes the factorWfrom Approach 1. Pruning makes the real running time much lower, since found branches disappear from the trie. - Space: O(T) for the trie, plus O(L) recursion depth. The board is marked in place.
Key Insights
- Search all words at once. The trie merges words with shared prefixes, so one DFS path serves all of them, and the cost no longer grows with the number of words.
- The trie is the pruning test. A path stops the moment its letters are not a prefix of any remaining word.
- Store the word on its end node. Reporting a match is then O(1), with no string building along the path.
- Clear found words and delete dead branches. Clearing prevents duplicates when a word can be traced in several places; deleting empty nodes keeps later DFS calls from re-entering exhausted branches.
- Mark cells in place. Overwriting a cell with
'#'and restoring it afterwards replaces a separate visited matrix.
Edge Cases
- A word that appears in several places: it must be reported once; clearing
wordafter the first match handles this. - One word is a prefix of another (
"oat"and"oath"): both live on the same trie path, and finding the shorter one must not stop the search for the longer one. - Single-cell board: only one-letter words can be found (Example 3).
- No word can be found: return an empty list.
- Every cell has the same letter (for example a 12 x 12 board of
'a'with words"a","aa", …, plus one word ending in'b'): the worst case for backtracking. Found words are cleared from the trie, but no node can be pruned, because every'a'node still leads toward the unmatched word ending in'b', so the search keeps going deep. - Words longer than the board has cells: they simply never match.
Common Mistakes
- Running Word Search once per word. It works on small inputs but repeats shared-prefix work and times out with up to 3 * 10^4 words.
- Reporting duplicates. Without clearing the word (or using a set), a word that can be traced twice appears twice in the output.
- Forgetting to restore the cell. A cell left as
'#'blocks every later search through it. - Stopping at the first found word on a path. After recording
"oat", the DFS must continue so"oath"can still be found. - Pruning before the recursion finishes. A node can only be removed after its own subtree has been explored, so the check belongs after the neighbour loop.
Interview Tips
- Start by mentioning that this is Word Search repeated for many words, and explain why the naive repetition is too slow.
- Introduce the trie as a way to share prefixes, then show how the DFS walks board and trie in lockstep.
- Write the trie insert and the DFS separately; storing the full word on the end node keeps the DFS short.
- Add pruning last and explain what it buys: once a branch is exhausted, later DFS calls stop one step earlier.
- Give the complexity in terms of the maximum word length, and note that it no longer multiplies by the number of words.
Follow-up Questions
- What if diagonal moves are also allowed? Use 8 directions; the bound becomes O(m * n * 8 * 7^(L-1)), and the trie logic is unchanged.
- What if a cell could be reused? Drop the in-place marking. Paths can then be unbounded, so cap them at the maximum word length (the trie depth does this automatically).
- How would you parallelize it? Split the starting cells across workers, each with its own copy of the board, and share a read-only trie (skip pruning or make it thread-safe).
- What if the board is fixed and many word lists are queried? Precompute all strings of length up to
Lreachable on the board into a trie or hash set, then answer each word with a lookup.