211. Design Add and Search Words Data Structure (Leetcode Problem)

@CodeChef @GeeksforGeeks @Leetcodes #leetcode #geeksforgeeks #adobe #amazon #microsoft #dailychallenge #technicalinterview #problemoftheday

Solution Code: Available in comment section

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

[viralSongsBollywood]

Solution Code:
class WordDictionary {
Trie dict;
public WordDictionary() {
dict=new Trie();
}

public void addWord(String word) {
Trie ptr = this.dict;
for(char c : word.toCharArray()){
if(ptr.letters[c - 'a'] == null)
ptr.letters[c - 'a'] = new Trie();
ptr = ptr.letters[c - 'a'];
}
ptr.end = true;

}

public boolean search(String word) {
return search(this.dict, word, 0);

}
public boolean search(Trie ptr, String word, int index){
if(index >= word.length()) return ptr.end;
char c = word.charAt(index);

if(c == '.'){
for(Trie t : ptr.letters){
if(t != null && search(t, word, index + 1))
return true;
}
return false;
}
if( ptr.letters[c - 'a'] == null) return false;

return search(ptr.letters[c - 'a'], word, index + 1);
}
class Trie{
Trie[] letters;
boolean end;
Trie(){
letters = new Trie[26];
end = false;
}
}

}

[ShivamGupta-cxhy]

Bas thoda jab tak aap problem ka naam bolte h and intro dete h tab tak question dikhaye .Amazing content 🔥🔥🔥