Problem
Given a board of characters and a list of words, return all words that can be formed by traversing adjacent cells (no reuse).
Example
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"]Solution
Build a Trie of the words. DFS each cell against the Trie. Mark cells visited with #.
def find_words(board, words):
trie = {}
for w in words:
node = trie
for ch in w: node = node.setdefault(ch, {})
node['#'] = w
result = []
def dfs(r, c, node):
ch = board[r][c]
if ch not in node: return
next_node = node[ch]
if '#' in next_node:
result.append(next_node['#'])
del next_node['#']
board[r][c] = '*'
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < len(board) and 0 <= nc < len(board[0]):
dfs(nr, nc, next_node)
board[r][c] = ch
for r in range(len(board)):
for c in range(len(board[0])):
dfs(r, c, trie)
return resultfunction findWords(board, words) {
const trie = {};
for (const w of words) {
let node = trie;
for (const ch of w) { if (!node[ch]) node[ch] = {}; node = node[ch]; }
node['#'] = w;
}
const result = [];
function dfs(r, c, node) {
const ch = board[r][c];
if (!node[ch]) return;
const next = node[ch];
if (next['#']) { result.push(next['#']); delete next['#']; }
board[r][c] = '*';
for (const [dr, dc] of [[0,1],[0,-1],[1,0],[-1,0]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length) dfs(nr, nc, next);
}
board[r][c] = ch;
}
for (let r = 0; r < board.length; r++)
for (let c = 0; c < board[0].length; c++) dfs(r, c, trie);
return result;
}struct Trie {
Trie* children[26] = {nullptr};
string word = "";
};
void dfs(vector<vector<char>>& board, int r, int c, Trie* node, vector<string>& result) {
char ch = board[r][c];
if (ch == '*' || !node->children[ch - 'a']) return;
Trie* next = node->children[ch - 'a'];
if (!next->word.empty()) {
result.push_back(next->word);
next->word = "";
}
board[r][c] = '*';
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < board.size() && nc >= 0 && nc < board[0].size()) dfs(board, nr, nc, next, result);
}
board[r][c] = ch;
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
Trie* root = new Trie();
for (auto& w : words) {
Trie* node = root;
for (char ch : w) {
if (!node->children[ch - 'a']) node->children[ch - 'a'] = new Trie();
node = node->children[ch - 'a'];
}
node->word = w;
}
vector<string> result;
for (int r = 0; r < board.size(); r++)
for (int c = 0; c < board[0].size(); c++) dfs(board, r, c, root, result);
return result;
}class TrieNode { TrieNode[] children = new TrieNode[26]; String word = null; }
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode node = root;
for (char ch : w.toCharArray()) {
if (node.children[ch - 'a'] == null) node.children[ch - 'a'] = new TrieNode();
node = node.children[ch - 'a'];
}
node.word = w;
}
List<String> result = new ArrayList<>();
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++) dfs(board, r, c, root, result);
return result;
}
private void dfs(char[][] b, int r, int c, TrieNode node, List<String> result) {
char ch = b[r][c];
if (ch == '*' || node.children[ch - 'a'] == null) return;
TrieNode next = node.children[ch - 'a'];
if (next.word != null) { result.add(next.word); next.word = null; }
b[r][c] = '*';
int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < b.length && nc >= 0 && nc < b[0].length) dfs(b, nr, nc, next, result);
}
b[r][c] = ch;
}Complexity
- Time: O(M(4ยท3^(L-1)))
- Space: O(N)
Explanation
Trie shares prefixes across multiple words. We can prune entire subtrees the moment a path doesn’t match any prefix.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?