Word Search II
You're given an m x n board of lowercase letters and a list of distinct words. Return every word from the list that can be traced on the board. You trace a word by starting at any cell and stepping to a horizontally or vertically adjacent cell for each next letter, never using the same cell twice within that word. Different words may share cells. Return each found word once, in any order.
Examples
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] returns ["eat","oath"]
"oath" runs o, a, t, h from the top-left corner, and "eat" reads right to left along row 1, starting from its last cell. The board has no p, so "pea" is impossible, and the only r has no a next to it, so "rain" fails.
board = [["a","b"],["c","d"]], words = ["abcb"] returns []
After a and b, the next letter c isn't next to b, since b touches only a and d. Even if it were, the final b would reuse a cell.
Constraints
- 1 <= board.length, board[0].length <= 12
- 1 <= words.length <= 3 * 10^4
Hints
Trying each word independently would be wasteful, how can you let words share their prefixes during the search?
Build a trie of all the words, then DFS the board from each cell along trie edges.
Insert every word into a trie. From each board cell, DFS while following trie children. On hitting an end-of-word node, record the word and clear its mark to avoid duplicates. Mark visited cells temporarily during recursion and prune trie nodes that have no children to keep the search small.
Drill This: Your Approach First
Approach
Put all the words into a trie so one walk of the board checks every word at once. From each cell, run a depth-first search that follows the matching trie child, stopping as soon as the letters so far aren't a prefix of any word. Mark a cell "#" while it's on the current path and restore it on the way back. When a node completes a word, record it and remove the word so it's found once, then prune branches left empty. O(m * n * 3^L) time, L = longest word; O(W) space, W = total letters in words.
Time
O(m * n * 3^L)
Space
O(W)
Pitfall
Solutions
class Solution {
private static class Node {
Node[] children = new Node[26];
String word;
}
public List<String> findWords(char[][] board, String[] words) {
Node root = new Node();
for (String w : words) {
Node node = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null) node.children[i] = new Node();
node = node.children[i];
}
node.word = w;
}
List<String> result = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs(board, i, j, root, result);
}
}
return result;
}
private void dfs(char[][] board, int i, int j, Node node, List<String> result) {
char c = board[i][j];
if (c == '#' || node.children[c - 'a'] == null) return;
node = node.children[c - 'a'];
if (node.word != null) {
result.add(node.word);
node.word = null; // dedupe
}
board[i][j] = '#';
if (i > 0) dfs(board, i - 1, j, node, result);
if (j > 0) dfs(board, i, j - 1, node, result);
if (i + 1 < board.length) dfs(board, i + 1, j, node, result);
if (j + 1 < board[0].length) dfs(board, i, j + 1, node, result);
board[i][j] = c;
}
}class Solution:
def findWords(self, board, words):
root = {}
for w in words:
node = root
for c in w:
node = node.setdefault(c, {})
node['$'] = w
result = []
rows, cols = len(board), len(board[0])
def dfs(i, j, node):
c = board[i][j]
if c not in node:
return
nxt = node[c]
if '$' in nxt:
result.append(nxt.pop('$'))
board[i][j] = '#'
for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
ni, nj = i + di, j + dj
if 0 <= ni < rows and 0 <= nj < cols and board[ni][nj] != '#':
dfs(ni, nj, nxt)
board[i][j] = c
if not nxt:
node.pop(c)
for i in range(rows):
for j in range(cols):
dfs(i, j, root)
return result