876764. Word Search II
Word Search II
Slug: word-search-ii Difficulty: Hard Id: 876764 Topic Tags: Trie, DFS, Backtracking, Advanced Data Structure Company Tags: None
Summary
The Word Search II problem involves finding all possible words in a given 2D grid of characters. The grid contains some hidden words that can be formed by connecting adjacent cells horizontally or vertically. The goal is to find all these hidden words using an efficient algorithmic approach.
Detailed Explanation
To solve this problem, we will use a combination of Trie data structure and Depth-First Search (DFS) with backtracking. We will first create a Trie from the given list of words. Then, for each cell in the grid, we will perform DFS to find all possible words that can be formed starting from that cell.
Here's a step-by-step breakdown of the solution:
- Create a Trie from the given list of words.
- Iterate over each cell in the grid.
- For each cell, use DFS to explore all possible paths starting from that cell.
- At each node in the DFS traversal, check if it matches any word in the Trie. If it does, add that word to the result set.
- Backtrack and continue exploring other paths until all possible words have been found.
Here's an ASCII art diagram of the Trie data structure:
+---+
| A |
+---+
/ \
+-----+-----+
| B | C |
+-----+-----+
/ \ /
+-------+-------+
| D | E | F |
+-------+-------+
Time complexity: O(M * N), where M is the number of words and N is the size of the grid. Space complexity: O(M), where M is the number of words.
Optimized Solutions
Java
import java.util.*;
public class WordSearchII {
public List<String> findWords(char[][] board, String[] wordDict) {
TrieNode root = new TrieNode();
for (String word : wordDict) {
insertWord(root, word);
}
Set<String> result = new HashSet<>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs(board, root, result, i, j);
}
}
return new ArrayList<>(result);
}
private void insertWord(TrieNode root, String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
if (!curr.children.containsKey(c)) {
curr.children.put(c, new TrieNode());
}
curr = curr.children.get(c);
}
curr.isEndOfWord = true;
}
private void dfs(char[][] board, TrieNode root, Set<String> result, int i, int j) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
return;
}
char c = board[i][j];
if (!root.children.containsKey(c)) {
return;
}
TrieNode next = root.children.get(c);
board[i][j] = '\0'; // mark as visited
if (next.isEndOfWord) {
result.add(String.valueOf(c));
}
dfs(board, next, result, i - 1, j); // up
dfs(board, next, result, i + 1, j); // down
dfs(board, next, result, i, j - 1); // left
dfs(board, next, result, i, j + 1); // right
board[i][j] = c; // backtrack
}
}