Create a word dictionary to add and search words.
You can also search using ‘.’ regular expression,
That is searching for the word “.at” will return true if the dictionary contains words like cat , mat etc since the first letter can be anything.
Try out the solution here:
https://leetcode.com/problems/design-add-and-search-words-data-structure/
Solution:
The solution to this problem is the same as here:
except for one change:
We need to be able to search for a word with ‘.’ character as a replacement for any character.
So we will modify our search logic alone.
If it is not a dot character then we implement the same search logic as before.
But if it is ‘.’ character , then we will go through all the children nodes of the current node and search for the remaining substring from each child node.
We will do this recursively.
If any of them match we return true , else we return false.
Here is the updated search logic:
public boolean searchTrie(String word,Trie input){
Trie node = input;
for(int i=0;i<word.length();i++){
char c = word.charAt(i);
if(c != '.'){
if(node.containsKey(c)){
node = node.get(c);
}else{
return false;
}
}
else{
for(int j=0;j<26;j++){
if(node.links[j] != null){
if(searchTrie(word.substring(i+1),node.links[j])){
return true;
}
}
}
return false;
}
}
return node!= null && node.isEnd;
}
As you see , if it is a ‘.’ character then we go through each child node of the current node and start the search for the remaining substring in the word.
Here is the entire code:
class WordDictionary {
Trie root ;
public WordDictionary() {
root = new Trie();
}
public void addWord(String word) {
Trie node = root;
for(int i=0;i<word.length();i++){
char c = word.charAt(i);
if(!node.containsKey(c)){
node.put(c,new Trie());
}
node = node.get(c);
}
node.setEnd();
}
public boolean search(String word) {
return searchTrie(word,root);
}
public boolean searchTrie(String word,Trie input){
Trie node = input;
for(int i=0;i<word.length();i++){
char c = word.charAt(i);
if(c != '.'){
if(node.containsKey(c)){
node = node.get(c);
}else{
return false;
}
}
else{
for(int j=0;j<26;j++){
if(node.links[j] != null){
if(searchTrie(word.substring(i+1),node.links[j])){
return true;
}
}
}
return false;
}
}
return node!= null && node.isEnd;
}
}
class Trie{
Trie[] links = new Trie[26];
boolean isEnd;
public void put(char c,Trie node){
links[c - 'a'] = node;
}
public Trie get(char c){
return links[c - 'a'];
}
public boolean containsKey(char c){
return links[c - 'a'] !=null;
}
public void setEnd(){
isEnd = true;
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
Time complexity:
For adding a word space complexity is O(m) where m is the length of the word.
For searching,
If there are no dots then time complexity remains the same as in the previous post , O(m) where m is the number of letters in the word.
For the worst case , if every letter is a dot,
Time complexity is O(26^m) because for every dot we will iterate the 26 child nodes to see which one is not null (assume the last node alone is not null) and then recursively do the same logic for m times. (m is the number of dots)
Space complexity:
For adding , space complexity is O(m)
For searching , it is O(m) in the worst case for the recursive stack.
That’s it!
Leave a Reply