Design Add and Search Words Data Structure | Made Easy | GOOGLE | Leetcode 211

This is the 5th Video of our Design Data Structure Playlist.
In this video we will try to solve a very very good problem "Design Browser History" (Leetcode - 211).
This is actually based on Trie Data Structure.

Share your learnings on LinkedIn, Twitter (X), Instagram, Facebook(Meta) with #codestorywithmik & feel free to tag me.

We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Design Add and Search Words Data Structure
Company Tags : GOOGLE

0:00 - Read the problem
0:44 - Best thing about Complex DS
1:58 - Understand the Problem
4:00 - Why TRIE ? + Template
5:10 - Example Dry Run + Explanation
15:44 - Story To Code Live

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[r.beditz]

Once again the best explanation, Trie is a new topic for me but still i was able to understand each and every step of the code.
Thankyou sir 😇
Below is the JAVA code for the solution if anyone needs :)

class WordDictionary {
public class TrieNode{
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord;
TrieNode(){
for(int i=0 ; i<26 ; i++)
this.children[i] = null;
isEndOfWord = false;
}
}

TrieNode root;

public WordDictionary() {
root = new TrieNode();
}

public void addWord(String word) {
TrieNode crawler = root;
for(int i=0 ; i<word.length() ; i++){
int index = word.charAt(i) - 'a';
if(crawler.children[index] == null)
crawler.children[index] = new TrieNode();
crawler = crawler.children[index];
}
crawler.isEndOfWord = true;
}

public boolean search(String word) {
return searchUtil(root, word);
}

public boolean searchUtil(TrieNode root, String word){
TrieNode crawler = root;
for(int i=0 ; i<word.length() ; i++){
char ch = word.charAt(i);
if(ch == '.'){
for(int j=0 ; j<26 ; j++){
if(crawler.children[j] != null)
if(searchUtil(crawler.children[j], word.substring(i+1)))
return true;
}
return false;
}
else if(crawler.children[ch - 'a'] == null)
return false;
crawler = crawler.children[ch - 'a'];
}
return crawler != null && crawler.isEndOfWord;
}
}

[souravjoshi]

Ek hi dil hai bhai, kitni baar jeetoge ❣

[codestorywithMIK]

Complexity Analysis:
Let’s say "n" as the length of the string being added,

For add():
Time: O(n), Space: O(n) because of the recursive calls

For search():
When there are no ‘.’ :
Time: O(n),
Space: O(n) because of the recursive calls

Where there are ‘.’:
The absolute worst case we can have 26 children at each node, traversing through all nodes with DFS will take 26^n (n nodes, each nodes have 26 children/characters).
Time: O(26^n),
Space: O(n) because we only have at max n calls on the stack at any given time.

[rahulmaurya]

very well explained, , always waiting for your video

[shikharpandya]

After watching ur trie video I did it myself thank u for everything

[vishalkurve]

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝ kardiya hai bhaiya.baki sab bhi kardo!

[sarthakgudwani]

Here is the Java Implementation :

public class WordDictionary {
private class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord;
}

private TrieNode getNode() {
TrieNode newNode = new TrieNode();
newNode.isEndOfWord = false;

for (int i = 0; i < 26; i++) {
newNode.children[i] = null;
}

return newNode;
}

private TrieNode root;

public WordDictionary() {
root = getNode();
}

public void addWord(String word) {
TrieNode crawler = root;

for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (crawler.children[index] == null) {
crawler.children[index] = getNode();
}

crawler = crawler.children[index];
}

crawler.isEndOfWord = true;
}

private boolean searchUtil(TrieNode root, String word) {
TrieNode crawler = root;

for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);

if (ch == '.') {

for (int j = 0; j < 26; j++) {
if (crawler.children[j] != null) {
if (searchUtil(crawler.children[j], word.substring(i+1))) {
return true;
}
}
}

return false;

} else if (crawler.children[ch-'a'] == null) {
return false;
}

crawler = crawler.children[ch-'a'];
}

return (crawler != null && crawler.isEndOfWord);
}

public boolean search(String word) {
return searchUtil(root, word);
}
}

[rajkrishanmahajan]

can please make video Weekly Contest also.

[kumarsaurabh]

sir ake bare placement preparation paie bhi video bana de jiea

[rupeshbiswas]

Previous video in this playlist is not about trie
Can u share the link?

[animesh]

class WordDictionary {
public:
unordered_set<string> st;
WordDictionary() {
st.clear();
}

void addWord(string word) {
st.insert(word);
}

bool search(string word) {
if(st.find(word)!=st.end()) return true;
for(auto str:st){
if(str.size()!=word.size()) continue;
int i=0, n=word.size();
while(i<n){
//cout<<word[i]<<" ";
if(word[i]=='.'){
i++;
//cout<<"C"<<endl;
continue;
}
else if(word[i]!=str[i]){
break;
}
i++;
}
//cout<<endl;
if(i==n){
//cout<<"True"<<endl;
return true;
}
}
return false;
}
};

class WordDictionary {
public:
vector<string> v;
WordDictionary() {

}

void addWord(string word) {
v.push_back(word);
}

bool search(string word) {
int count=0;
int n=word.size();
for(int i=0; i<v.size(); i++){
if(n==v[i].size()){
for(int j=0; j<n; j++){

count++;
}
else{
count=0;
break;
}
}
if(count==n) return true;
}
}
return false;
}
};

first code give TLE but second not why?