Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Constraints:
- 1 <= board.length <= 12
- 1 <= board[i].length <= 12
- 1 <= words.length <= 3 * 10^4
- 1 <= words[i].length <= 10
- board and words consists of only lowercase English letters
Examples:
Input: [["o","a","a","n"],"o","i","n"],"ean"],[["p","e","a","r"],"o","a","a","n"],"rain"],[["m","e","a"],"o","a","o","i","n"],"me"]
Output: ["oath","pea","eat","rain"]
Explanation: The words can be found as follows: o-a-t-h, p-e-a, e-a-t, r-a-i-n
Solutions
Trie and Depth-First Search
The solution uses a Trie data structure to store the words and then uses depth-first search to find all words in the board. The Trie is constructed by iterating over each word and adding each character to the Trie. Then, for each cell in the board, we start a depth-first search from that cell and explore all possible words that can be formed from that cell. If a word is found, it is added to the result list and the word is removed from the Trie to avoid duplicates.
class Solution {
class TrieNode {
HashMap<Character, TrieNode> children = new HashMap<>();
String word;
public TrieNode() {
}
}
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (!node.children.containsKey(c)) {
node.children.put(c, new TrieNode());
}
node = node.children.get(c);
}
node.word = word;
}
List<String> res = new ArrayList<>();
boolean[][] visited = new boolean[board.length][board[0].length];
int[][] directions = {
{
0, 1}
, {
0, -1}
, {
1, 0}
, {
-1, 0}
}
;
public void dfs(int i, int j, TrieNode node) {
if (node.word != null) {
res.add(node.word);
node.word = null;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || !node.children.containsKey(board[i][j])) return;
visited[i][j] = true;
char temp = board[i][j];
board[i][j] = '#';
for (int[] dir : directions) {
dfs(i + dir[0], j + dir[1], node.children.get(temp));
}
board[i][j] = temp;
visited[i][j] = false;
}
for (int i = 0;
i < board.length;
i++) {
for (int j = 0;
j < board[0].length;
j++) {
dfs(i, j, root);
}
}
return res;
}
}Follow-up:
How would you optimize the solution to handle a large number of words?
