/**
212. Word Search Two
Given an m x n board of characters and a list of strings words, return all words on the board.
Each word must be constructed from letters of sequentially adjacent cells,
where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example 1:
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”]
Example 2:
Input: board = [[“a”,”b”],[“c”,”d”]], words = [“abcb”]
Output: []
*/
See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/trie/WordSearchTwo.java
See implementation of the trie used in this code here:
https://github.com/zcoderz/leetcode/blob/main/src/main/java/utils/TrieNode.java
This solution is very interesting in that it uses the trie data structure to efficiently solve the question.
Observation:
- We are given a list of words and are asked to check whether these words exist in the two-dimensional array
- So, we need to traverse the board and determine the set of words that exist on the board
- Since words can be share the same prefix, for example dog, dogs, doggy, dogfood etc we would ideally not want to re-traverse the matrix multiple times for each common group in the words. A trie data structure would serve here well.
- We can populate the trie data structure with the list of words and then traverse the matrix matching each character in the trie until the trie has been traversed.
Algorithm:
- Populate a trie data structure with list of words
- Traverse the matrix with possible word matches in trie
- When a matching word is found add it to a list and remove the word market from trie node so that the word doesn’t repeat
- Return the list of words found above in step 3 as the answer
Optimization:
- When traversing a node in the trie , after a node has been traversed and thus its matches have been discovered, remove the node from its parent trie if it doesn’t have any children. This strategy gradually prunes the trie and thus prevents wasting time on unneeded cycles.
Here is the code:
public List<String> findWords(char[][] board, String[] words) {
//construct the trie from the words
TrieNode root = new TrieNode();
root.buildTrie(words);
int maxRows = board.length;
if (maxRows == 0) return wordsFound;
int maxCols = board[0].length;
if (maxCols == 0) return wordsFound;
for (int iRow = 0; iRow < maxRows; iRow++) {
for (int iCol = 0; iCol < maxCols; iCol++) {
char boardChar = board[iRow][iCol];
TrieNode cNode = root.getChildNode(boardChar);
if (cNode != null) {
traverseBoard(board, cNode, iRow, iCol);
}
}
}
return wordsFound;
}
void traverseBoard(char[][] board, TrieNode node, int row, int col) {
char boardChar = board[row][col];
if (node.getWord() != null) {
wordsFound.add(node.getWord());
node.setWord(null);
}
int maxRows = board.length;
int maxCols = board[0].length;
board[row][col] = '#';
for (int[] move : moves) {
int tmpRow = row + move[0];
int tmpCol = col + move[1];
if (tmpRow >= 0 && tmpCol >= 0 && tmpRow < maxRows && tmpCol < maxCols) {
char boardCharNew = board[tmpRow][tmpCol];
TrieNode cNode = node.getChildNode(boardCharNew);
if (cNode != null) {
traverseBoard(board, cNode, tmpRow, tmpCol);
if (cNode.getChildChars().isEmpty()) {
//Optimization
//Gradually prune the nodes in Trie during the backtracking.
//The idea is motivated by the fact that the time complexity of
//the overall algorithm depends on the size of
//the Trie. For a leaf node in Trie, once we traverse it (i.e. find a matched word),
//we would no longer need to traverse it again.
//As a result, we could prune it out from the Trie.
//Gradually, those non-leaf nodes could become leaf nodes later
//since we trim their children leaf nodes.
//This pruning measure could reduce up to 50% of the running time
//for the test cases of the online judge.
node.removeChar(boardCharNew);
}
}
}
}
board[row][col] = boardChar;
}