DSA
Word Search II
Trie. Time O(m×k×4^L), Space O(L).
Practice Link
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.
Intuition#
Searching for each word individually with a plain DFS (like Word Search) works, but re-scans the whole board once per word — O(words × m×n×4^L). Since many words share prefixes, a Trie lets us search for all words at once: build a trie of every word, then DFS from every board cell, walking down the trie as we walk the board. Once a trie node is isEnd, we've found a word.
Key details in the implementation:
- Each TrieNode also stores the full word at its terminal node, so we can push the match directly instead of rebuilding the string from the path.
- DFS moves the curr trie pointer forward together with the board position. If board[i][j] has no matching child in the trie, that path is dead — prune immediately.
- Standard backtracking marks the visited cell with '*' before recursing into neighbors, then restores it after, so a cell isn't reused within the same word.
- After a match is recorded, curr->isEnd is set back to false so the same word isn't pushed twice if the board contains multiple paths to it.
- Directions are stored as dx/dy arrays and checked against board bounds before indexing.
Solution#
class TrieNode{
public:
bool isEnd;
string word;
TrieNode* children[26];
TrieNode()
{
isEnd = false;
for(int i=0;i<26;i++){
children[i] = NULL;
}
}
};
class Solution {
public:
vector<int> dx = {1,0,-1,0};
vector<int> dy = {0,1,0,-1};
void insertIntoTrie(string word, TrieNode* root){
TrieNode* curr = root;
for(char c: word){
int idx = c - 'a';
if(curr->children[idx] == NULL){
curr->children[idx] = new TrieNode();
}
curr = curr->children[idx];
}
curr->isEnd = true;
curr->word = word;
}
void DFS(vector<vector<char>>& board, vector<string> &ans, TrieNode* curr, int i, int j){
if(i < 0 || i>= board.size() || j<0 || j>=board[0].size() || board[i][j] == '*' || curr->children[board[i][j]-'a'] == NULL){
return;
}
curr = curr->children[board[i][j] - 'a'];
if(curr->isEnd){
ans.push_back(curr->word);
curr->isEnd = false;
}
char c = board[i][j];
board[i][j] = '*';
for(int dir=0;dir<4;dir++){
int ni = i + dx[dir];
int nj = j + dy[dir];
DFS(board, ans, curr, ni, nj);
}
board[i][j] = c;
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
TrieNode* root = new TrieNode();
for(auto word: words){
insertIntoTrie(word, root);
}
vector<string> ans;
TrieNode* curr = root;
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
DFS(board, ans, curr, i, j);
}
}
return ans;
}
};
Complexities#
Let n = number of words, L = max word length, m×k = board dimensions.
Time Complexity: O(n × L) to build the trie, plus O(m×k×4^L) for the DFS over the board in the worst case (bounded much lower in practice since dead trie paths are pruned).
Space Complexity: O(n × L) for the trie, plus O(L) recursion stack depth per DFS call.