Problem
Given an m × n board of characters and an array of strings words, return all words that can be formed in the board.A word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring.
The same cell may not be used more than once while constructing a word.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words = ["oath","pea","eat","rain"]Output
["oath","eat"]Solution
This solution uses a Trie together with Backtracking. The Trie stores all words so that the search can determine whether the current path is a prefix of any word.The board is then searched from every cell. At each cell, the algorithm follows the corresponding Trie node and continues in the four possible directions: up, down, left, and right.
When a Trie node contains a complete word, that word has been found and is added to the result. The word is then cleared from the Trie node to prevent adding the same word multiple times.
The current cell is temporarily marked as visited so that it cannot be reused in the same path. After the recursive search finishes, the original character is restored. This is the backtracking step.
If the current character does not exist in the Trie, the search stops immediately. This allows the Trie to prune paths that cannot form any word.
class Solution {
static class TrieNode {
TrieNode[] children = new TrieNode[26];
String word;
}
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<>();
TrieNode root = new TrieNode();
// Build the Trie.
for (String word : words) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
int index = ch - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.word = word;
}
// Start searching from every cell.
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[0].length; col++) {
backtrack(board, row, col, root, result);
}
}
return result;
}
private void backtrack(char[][] board, int row, int col,
TrieNode node, List<String> result) {
// Check boundaries and visited cells.
if (row < 0 || row >= board.length ||
col < 0 || col >= board[0].length ||
board[row][col] == '#') {
return;
}
char ch = board[row][col];
TrieNode next = node.children[ch - 'a'];
// No word has this prefix.
if (next == null) {
return;
}
// A complete word is found.
if (next.word != null) {
result.add(next.word);
// Prevent finding the same word again.
next.word = null;
}
// Mark the cell as visited.
board[row][col] = '#';
// Explore all four directions.
backtrack(board, row - 1, col, next, result);
backtrack(board, row + 1, col, next, result);
backtrack(board, row, col - 1, next, result);
backtrack(board, row, col + 1, next, result);
// Undo the choice.
board[row][col] = ch;
}
}
Complexity
LetW be the number of words, L be the maximum word length, and M × N be the size of the board.
Building the Trie takes
O(W × L) time and O(W × L) space in the worst case.
The backtracking search is pruned by the Trie. In the worst case, the search can explore up to
O(M × N × 4 × 3L - 1) paths, although the Trie significantly reduces unnecessary searches for typical inputs.
The recursion depth is at most
O(L), excluding the space required for the Trie and output.