Word Search in Trie
Sometimes we need to search for a word in a grid of letters (like Boggle or Word Search). A trie can be used to efficiently check if a word exists without re-checking prefixes repeatedly. The problem: Given a 2D board and a list of words, find which words can be formed.
Approach using trie:
1. Insert all words into a trie.
2. For each cell in the board, start DFS search, moving in four directions.
3. At each step, check if current path forms a valid prefix; if not, prune.
4. When a node is end-of-word, add the word to results.
This is a classic backtracking problem that becomes efficient with trie pruning.
Java skeleton (DFS on board with trie):
public List findWords(char[][] board, String[] words) {
Trie trie = new Trie();
for (String w : words) trie.insert(w);
Set result = new HashSet<>();
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs(board, i, j, trie.root, new StringBuilder(), visited, result);
}
}
return new ArrayList<>(result);
}
private void dfs(char[][] board, int i, int j, TrieNode node, StringBuilder sb, boolean[][] visited, Set result) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j]) return;
char c = board[i][j];
TrieNode child = node.children[c - 'a'];
if (child == null) return;
sb.append(c);
if (child.isEndOfWord) result.add(sb.toString());
visited[i][j] = true;
dfs(board, i+1, j, child, sb, visited, result);
dfs(board, i-1, j, child, sb, visited, result);
dfs(board, i, j+1, child, sb, visited, result);
dfs(board, i, j-1, child, sb, visited, result);
visited[i][j] = false;
sb.setLength(sb.length() - 1);
}
Two Minute Drill
- Word search on board with trie enables efficient prefix pruning.
- DFS from each cell, backtrack, use visited set.
- Trie stops exploring invalid prefixes early.
- Time complexity: O(m * n * 4^L) worst but pruned heavily.
Need more clarification?
Drop us an email at career@quipoinfotech.com