Given a m*n board of letters and a list of words , find those words present in the board.
For example,
Given the board:
and the below list of words:
["oath","pea","eat","rain"]
The output is
“eat” ,”oauth”
Try out the solution here:
https://leetcode.com/problems/word-search-ii/solution/
Solution:
Let’s use Trie data structure to solve this problem.
We could use a hash set or hash map.
But Trie is better for the following use cases:
- If you want to retrieve all words matching the given prefix
- If you want to collect all the words in alphabetical order
- If the data set is so huge that using a hash table would result in hash collisions.
Our problem doesn’t involve any of the above use cases.
Still let’s use it to understand Trie datastructure better.
First we will prepare the Trie data structure for the words we want to search for.
Then we will use backtracking:
Starting from each cell in the board we will search for the letters starting from that cell in the Trie recursively.
If one letter matches then the next letter will be searched for in all four directions.
If we find a matching word during this process, we will add it to output.
STEP 1: Create the data structure
Let’s first create the Trie data structure:
class Trie{
Map<Character,Trie> children = new HashMap<>();
String word = null;
public boolean containsKey(char letter){
return children.get(letter) != null;
}
}
The trie data structure has a map.
The map is used to store a character and a node to link the character to the next node.
It has a string variable representing the word .
We use this to represent a leaf node.
It will contain the actual word represented by the path ending with the leaf node.
So if the word is null then it means it is not a leaf node.
containsKey() method will check if the given string is present in the Trie or not.
STEP 2: Populate the Trie
Let’s now build the Trie data structure for the given list of words.
Here is the logic to do the same:
Trie root = new Trie();
for(String word:words){
Trie node = root;
for(int i=0;i<word.length();i++){
char c = word.charAt(i);
if(!node.containsKey(c)){
node.children.put(c, new Trie());
}
node = node.children.get(c);
}
node.word = word;
}
We see if the trie already has the node , if yes we move to it else we put a new node for the given character and move to the new node.
STEP 3: Backtrack until you find the given words:
To backtrack you start from the first cell in the board, see if the Trie contains that letter and search in all four directions for the remaining letters of each word.
You keep backtracking during the process .(ignore a path if the current search fails and go back to the point where it last succeeded and proceed in a new direction)
Here is the code to do backtracking:
public void backtrack(int row,int col,Trie root){
//get the letter from the board
char letter = board[row][col];
// get the child node for this letter in the trie
Trie node = root.children.get(letter);
//if it is the leaf node add the word to the output
if(node.word != null){
output.add(node.word);
node.word = null; //to prevent duplicates
}
// to make sure same character is not searched again mark it as #
board[row][col] = '#';
//search in all four directions - UP,DOWN,LEFT AND RIGHT
int[] rows = new int[]{-1,1,0,0};
int[] cols = new int[]{0,0,-1,1};
for(int i=0;i<4;i++){
int r = row+rows[i];
int c = col+cols[i];
if(r < 0 || c < 0 || r >= board.length || c >= board[0].length) continue;
if(node.containsKey(board[r][c])){
backtrack(r,c,node);
}
}
//change # character back to the original letter so that it can be processed in the next search
board[row][col] = letter;
// to remove words once matched so that code executes faster
if(node.children.isEmpty()){
root.children.remove(node);
}
}
As you noticed,
in backtracking we follow the below steps:
- Get the current letter from the board
- Get the child of the current letter from the Trie
- Mark the current letter in the board as # so that it is not searched again (while backtracking in four directions)
- Search if the next letter is in the children of the current node if yes continue backtracking for that letter
- Mark the current letter in the board back to the letter.
We have done few optimizations in the above code:
- Once a word is added to the output we remove it from the leaf node so that there are no duplicates added ( the comment “to prevent duplicates” is written next to the code above)
- Once a word is matched we remove the leaf nodes recursively
You might be wondering if the first step takes care of removing the duplicates then why we need the second step.
The second step only removes the leaf nodes so that they are not searched again.
It won’t prevent all duplicates because:
If the same word is present twice or more in the board and if that word is a prefix for another word then it wont be removed in the recursive code (since it has “children”)
For example:
In the above example , there are two words represented by the Trie:
“go” and “got”
Let’s say we want to search both the words.
According to the recursive logic in our code we will remove the leaf nodes once a match is found but only if they don’t have children.
So once the “go” word is matched in the trie we wont remove the word from the trie as it has a child “t” to represent the word “got”.
So we need to add extra logic to prevent duplicates (remove the word from the node so that it is no more a leaf node)
We will remove the word “go” from the node “o” so that it is no more considered a leaf node.
Here is the entire code:
class Solution {
List<String> output = new ArrayList<>();
char[][] board;
public List<String> findWords(char[][] board, String[] words) {
//prepare Trie
this.board = board;
Trie root = new Trie();
for(String word:words){
Trie node = root;
for(int i=0;i<word.length();i++){
char c = word.charAt(i);
if(!node.containsKey(c)){
node.children.put(c, new Trie());
}
node = node.children.get(c);
}
node.word = word;
}
for(int i=0;i<board.length;i++){
for(int j =0;j<board[i].length;j++){
if(root.containsKey(board[i][j]))
backtrack(i,j,root);
}
}
return output;
}
public void backtrack(int row,int col,Trie root){
char letter = board[row][col];
Trie node = root.children.get(letter);
if(node.word != null){
output.add(node.word);
node.word = null; //to prevent duplicates
}
board[row][col] = '#';
int[] rows = new int[]{-1,1,0,0};
int[] cols = new int[]{0,0,-1,1};
for(int i=0;i<4;i++){
int r = row+rows[i];
int c = col+cols[i];
if(r < 0 || c < 0 || r >= board.length || c >= board[0].length) continue;
if(node.containsKey(board[r][c])){
backtrack(r,c,node);
}
}
board[row][col] = letter;
// to remove words once matched
if(node.children.isEmpty()){
root.children.remove(node);
}
}
class Trie{
Map<Character,Trie> children = new HashMap<>();
String word = null;
public boolean containsKey(char letter){
return children.get(letter) != null;
}
}
}
Time complexity:
For every cell in the board we search in all 4 directions.
So approximately the worst case complexity is O( 4 ^ n)
where n is the number of letters in the board.
Space complexity:
For each letter in the board we make a recursive call in the worst case.
So the memory for the recursive stack is O(n) which is the space complexity.
That’s it!
Leave a Reply