Design Add and Search Words Data Structure - Leetcode 211 - Python

[@NeetCode]

🌲 Tree Playlist: kzbin.info/www/bejne/hZ-2n2WOerZng7s

[@izzyjmiles]

I don't normally comment on videos, but your tutorials have easily made the biggest difference in my preparation for applying to big tech. Please don't stop making them as they can and should become the most popular videos on KZbin for interview prep. Seriously, thank you!

[@OogaBooga3806]

Have you landed a position yet? Hope your hunt has been fruitful.

[@izzyjmiles]

@@OogaBooga3806 I have! I am currently working at Microsoft :) I got offers from multiple bay area startups, Audible and got to a second final round with Google (which means I was close). I owe a lot of this to NeetCode and a consistent study habit!

[@OogaBooga3806]

@@izzyjmiles Congrats man!! Really happy to hear that! Good for you for putting in the hard work to get to this point! :)

[@HannanShah-hq4wx]

@@izzyjmiles did the bay area startups ask you lc and system design, or was it mostly behavioral? Congrats btw!!

[@izzyjmiles]

@@HannanShah-hq4wx if I remember it was leetcode, take home projects and behavioral. Even a bit of system design. I remember turning a few companies down bc they wanted me to build ridiculous projects like an MVP of Slack. Not sure what current interviews are like though given all the AI advancements

[@Lulit999]

For those getting TLE: storing the longest word length will provide mich better runtime (because we wont look for words longer than current longest word). So in code add the following lines: 1) In __init__ method: self.max_word_length = 0 2) in addWord method: self.max_word_length = max(self.max_word_length, len(word)) 3) in search method: if len(word) > self.max_word_length: return False

[@anyangli918]

That's super helpful. Reduced my run time from 10700 ms to 6300ms!

[@deviantstar3836]

You may also put all the matched words into set. Next time you meet them you wont be running dfs to find out if it matches. Makes it little bit faster 1) In _init_ method: self.wordcheck=set() 2) in search method: if word in self.wordcheck: return True if dfs(self.root, 0): self.wordcheck.add(word) return True else: return False

[@jean4j_]

That's brilliant!

[@GingeBreadBoy]

""" (node contains bad and bass) if looking for bad, each char is in curr.children, so we're good for "b.ss", we'd backtrack at i=1, letting it take on each of the possible values For the below code, default runtime wont be that good. Each layer gives up to 26 options, so 26**n. However, if our max word length was 3, and we have "a....."", we don't want to run for all those extra calls, we'll never find them. So we store max word length and use it to validate search calls. Moreover keep a recall set for queries with "." inside, so we can quickly return True if similar/same queiries are run. """ class TrieNode: def __init__(self): self.children = {} self.end_of_word = False class WordDictionary: def __init__(self): self.root = TrieNode() #to ensure we don't search for words that can't exist self.max_word_length = 0 #If we search same thing in the future can be faster self.recall_set = set() def addWord(self, word: str) -> None: #current node curr = self.root #update max word length self.max_word_length = max(len(word), self.max_word_length) #for each character add or find for char in word: #create new node if char not in curr.children: curr.children[char] = TrieNode() #move to next node curr = curr.children[char] #mark end of word curr.end_of_word = True def search(self, word: str) -> bool: #short circuit if word can't exist inside Trie if len(word) > self.max_word_length: return False #word has already been found if word in self.recall_set: return True #requires depth first search to account for "." def dfs(i, node): for j in range(i, len(word)): #word j doesn't exist #backtrack all possibilities if word[j] == ".": #check each possible child Trie for child in node.children.values(): if dfs(j+1, child): #add the word to our recall set once found self.recall_set.add(word) return True return False else: if word[j] not in node.children: return False #move to next letter node = node.children[word[j]] #we've finshed looping through characters #and have found eow as True (meaning word is found) return node.end_of_word #begin searching return dfs(0, self.root) Here are the ideas implemented

[@BABA-oi2cl]

@@GingeBreadBoy thanks a lot, i wasn't able to get what the top comment was trying to say at first. Your implementation explained everything (❁´◡`❁)

[@DayoAjayi]

I love your step-by-step breakdown of the problems and thorough analysis before jumping into the coding segment. Your channel has been INVALUABLE in my interview prep. Thank you for all you do.

[@sellygobeze7173]

Amazing Video again Neetcode! For those hitting TLE error or would like a slightly more intuitive (IMO) & optimized solution for the search function, see below: def search(self, word): def dfs(trie, i): current = trie if i == len(word): return current.endOfWord char = word[i] if char != '.': if char not in current.children: return False return dfs(current.children[char], i + 1) else: for child in current.children: if dfs(current.children[child], i + 1): return True return False return dfs(self.root, 0) base case: if i == len(word): #meaning each char is correct# return current.endOfWord recursive case: - (easy) if char != '.' :#meaning its a normal trie search# check if char doesn't match, if it does, change currentTrie to the child's trie and increment i - (more challenging) otherwise: for each child in current's children, if any of their dfs() return true, return true if none do, return false Thanks Neetcode!

[@patriciam6184]

Your videos are making my Leetcode Premium subscription obsolete :) Don't even need to check the LC solutions anymore, I just come straight here.

[@The6thProgrammer]

Very nice video! My approach was slightly different, using pure recursion to advance cur to the next child in both the "." and "a" - "z" cases. I also used an array of 26 values to hold the child nodes. Because we know we will always have at most 26 children, I feel the array data structure is superior here as the memory consumption is fixed, we have contiguous elements in memory for faster access during iteration (and better cache performance). Here is my dfs function (in C++). bool dfs(string word, WordDictionaryNode* curr, int i, int n) { if (i == n) { return (curr != nullptr) && (curr->isWord); } if (word[i] == '.') { for (auto& child : curr->children) { if (child != nullptr && dfs(word, child, i + 1, n)) { return true; } } } else { if(curr->children[word[i] - 'a'] != nullptr) { return dfs(word, curr->children[word[i] - 'a'], i + 1, n); } } return false;

[@HalfJoked]

For those getting Time Limit Exceeded - this answer is correct, it's just LeetCode being LeetCode, the internal processing time can delay and TLE even if it shouldn't. Try running it *several* times.

[@deviantstar3836]

@Bogdan Shmat you may put matched words into set. Next time you meet them just return true insted of running dfs again. You also can keep track of the longest word in Trie. If the word you are searching is longer than the longest word return false. This two optimizations will put you in nearly 90%

[@zhengweimichaelbai8015]

@@deviantstar3836 It does work! That's genius!

[@mohdkamleh2345]

if you get TLE use hashmap to store words before adding them and if word does not contain '" ," just return hashmap result also before return in sear func if word contains dot then just dp result before returning it and on every new word add clear dp

[@play005517]

I love leetcode forcing you to defeat the purpose of using an advanced data structure like Trie and go back to using plain old hashset in order to even be considered passing bare minimum time limit

[@halahmilksheikh]

18:29 Another scenario the "return cur.word" is used is "ab*" . j will be 3 so it won't go into the forloop. It'll go straight to the cur.word where root is the last node so cur.word returns true.

[@ShailPM]

tf is your youtube channel

[@dj1984x]

yesterday, i didn't know what a trie was today, i do thanks neetcode I should add, I particularly like the trie data structure. It is intuitive and simple, quite easy to follow and implement. A good example of a helpful data structure

[@oooo-rc2yf]

Using DFS to get around the wild cards is very celever

[@licokr]

Easy to understand 👍somehow, I solved this problem using queue and DFS but the '.' part was implemented using BFS.... code was kind of tricky. Your code is more concise and readable. Thanks a lot! I always learn a lot from your videos!

[@fraswasim8543]

I just wanted to add to the explanation since it took me a couple moments to notice why this works. Suppose you had a search term with a wild card at the end, for example : 'ab.' On the iteration of the wild card it would go into the 'if c == "."" and then call dfs again with the word index "i+1" set out of bounds of the word - an empty string - so the final dfs will only check whether any word finishes on that wild card.

[@mirrorinfinite5392]

thanks for the explanation!

[@mehulsolanki9435]

Well if you are solving this problem right now, Leetcode seems to have added some additional test cases which can give you TLE. For example, in the video - the code runs in 348 ms but it is better than 38.76 % , mine ran in 11861 ms !! , but it was still faster than 73.5 % of Python submissions, resubmit it - it should accept eventually.

[@digglejiggley1762]

I came here to say that too. I keep getting TLE. Did it get accepted eventually? Mine seems to show no change

[@Babe_Chinwendum]

@@digglejiggley1762 Same with me. How did it go?

[@Babe_Chinwendum]

Update: Just ran it now, it worked

[@MaxFung]

The DFS confuses me, how on earth does passing the child into the function validating that a valid character exists on the child's child?

[@symbol767]

It seems leetcode updated the test cases for this problem because the time complexity is insane now, its giving me 17,000ms+ runtime even with your exact solution.

[@chair_smesh]

same

[@tayjen59]

I implemented bfs, with extra space complexity, but it gives me ~10,000ms

[@ireggae]

are you able to pass the tests? It seems to fail for me now using exact solution?

[@ΚωνσταντίνοςΞανθόπουλος-ο6υ]

Use memoization to pass the tests. Still slow (kinda), but it gets the job done

[@PippyPappyPatterson]

@@ΚωνσταντίνοςΞανθόπουλος-ο6υ Can you post your memoization solution?

[@xBazilio]

It is possible to speed up the search with dots by saving word tail length in the Node. that way you wouldn't need to investigate a child if it doesn't have enough children. when adding a word calculate $tail = $len - $i - 1; (it's PHP). then add it this way $node->tail = max($node->tail, $tail); then when searching do if ($child->tail < $tail) { continue; }

[@tds456]

This brought the python answer from 18426 ms -> 5484 ms, faster than 96.70%. Awesome idea.

[@rackstar2]

@@tds456 hey do you mind posting your python solution here ?

[@tds456]

@@rackstar2 class WordDictionary: def __init__(self): self.root = TrieNode() def addWord(self, word: str) -> None: pos = self.root for i in range(0, len(word)): c = word[i] pos.length = max(pos.length, len(word)-i) if c not in pos.children: pos.children[c] = TrieNode() pos = pos.children[c] pos.end = True def search(self, word: str) -> bool: def sub_search(index: int, pos: TrieNode) -> bool: for i in range(index, len(word)): c = word[i] if c == '.': sublen = len(word) - i - 1 for child in pos.children: if pos.children[child].length < sublen: # child doesn't have a long enough length to check continue if sub_search(i+1, pos.children[child]): return True return False else: if c not in pos.children: return False pos = pos.children[c] return pos.end return sub_search(0, self.root)

[@s8x.]

search function is insane

[@leonscander1431]

For those who are confused with mixin iterative and recursive approach. Here's completely recursive solution: def search(self, word: str) -> bool: def dfs(root: Optional[TrieNode], i: int) -> bool: if i == len(word): return root.isEnd char = word[i] if char == ".": for node in root.children.values(): if dfs(node, i + 1): return True else: if root.has(char): return dfs(root.get(char), i + 1) return False return dfs(self.root, 0)

[@jeffreylee911]

The best explanation on youtube!

[@harinijaan3779]

Your approach to the problem is so good . But in my opinion you can write the code in more elegant way by not mixing up recursive and iterative part

[@harinijaan3779]

def dfs(node, i): if i == len(word): return node.end_node if word[i] == ".": for child in node.children: if dfs(node.children[child], i+1): return True if word[i] in node.children: return dfs(node.children[word[i]], i+1) return False

[@Eeeason-c5y]

Why mixing up recursive and iterative part is because the problem constrain the num of '.' to be up to 2, so the most cases are deterministic characters. If we just use recursive, it may face stack overflow, while it's convenient to deal with '.' with recursive, so the code is end up with recursive and iterative.

[@ivantishchenko4686]

It's an amazing explanation as usual. Your videos are the main point of contact, if I am stuck on the solution. Please keep going with your videos! 👍👏

[@konarklohat8195]

I solved it using a hashmap by connecting the size of the added strings with a vector of strings associated with the same sizes. unordered_map

[@halahmilksheikh]

This is such a weird DFS. The base case isn't at the top and there are 4 (!) different returns and there's an interleaved iterative part too... it all feels so inelegant and held together by duck tape yet somehow works. That's crazy how anyone can figure this out on the fly without ever seeing this before

[@PippyPappyPatterson]

I don't think anyone does within interview time limits.

[@LightningSpeedtop]

My thoughts exactly, anyone that comes up with this in an interview setting is good. The code itself looks spaghetti like

[@weishin]

This actually results in a time limit exceeded for one of their tests. They might have updated their test or something

[@burhanuddinmerchant]

did you find a solution to this?

[@weishin]

@@burhanuddinmerchant yes and no. I did look at other possible solutions that would fix this such as using a stack instead of recursion or storing the words in the dictionary as (len(word) -> word) for key value pair. I believe the problem occurs in the recursion step because the code has to search every step. No as in I did not attempt to code it on my own. I found solutions that get over this issue via researching the discussion tab on leetcode During an interview I would expect this question to come up but if you were to give this solution I would expect a follow up on "What if you have a billion words how would you optimize"

[@burhanuddinmerchant]

@@weishin gotcha 👍, replacing the recursive dfs with an iterative one seems like a good idea.

[@torin755]

Just did it now, it is at ~19,000ms but still got accepted.

[@eshaanmandal3466]

replaced the hashmap with TrieNode[] children; it works now but takes ~ 1600 ms

[@minseoppark3117]

I guess BFS forr search method would be easier and straightforward to think because we don't have to think about "." condition. For example, def search(self, word: str) -> bool: nodes = [self.root] for i in range(len(word)): next_nodes = [] w = word[i] for node in nodes: for v, child in node.children.items(): if v == w or w == ".": next_nodes.append(child) nodes = next_nodes if i == len(word) - 1: for n in nodes: if n.eod: return True return False But always thanks for the video, pretty much helping me to study by myself

[@DED_Search]

what is the time and space complexity of this one? Thanks.

[@animaltrainer88]

Say ; N : # of words W: Average word length Then ; Space Complexity : O(N*W) AddWord function Time Complexity: O(W) Search Time Complexity Best Case : O(W) (if trie not backed by a hash set , if it's backed by a set then the best case is O(1)) Search Time Complexity Worst Case : O(26^W) (if all dots)

[@jhonsen9842]

Infact this is a Hard Problem not sure why it is in the list of Medium.

[@meechos]

There is a bug in the problem's respective code snippet on your website, second line from the end `cur.end` should be `cur.word`. Thanks for your brilliant work.

[@zheyu2701]

Same here

[@m____s]

Using stack with the word index is more intuitive.

[@harunguven8581]

I used bfs in this problem to handle tricky "." situations. But more code is required to implement bfs.

[@sebastiantu6212]

Is there a benefit to using a TrieNode class over just a dictionary? Feel like the only thing it adds is the .end flag, but you can just add a symbol as a child to denote the end. And then it doesn't take up all that extra space on the stack

[@dera_ng]

Wow! Another great video. I wish there was more that I could do than just text "thank you".... So I had solved this from another video you made on backtracking and I also thought of how to end the recursion immediately a "." (period character) was found. I thought of raising an exception. Thereafter, I called the backtrack function in a try block which on successful run would return False; however if there was an exception called anywhere in the call stack, it would be caught by the except block and immediately return True. Do you think the use of an exception to immediately quit out of a recursive function is something interviewers would frown upon? I mean, it gets the job done and I don't think there is a hit on performance. I stand to be corrected. Thanks again.

[@GabrielGamesYTG]

I made this exercise before watching the video and I did an interesting "iterative solution" that consist in multiple queues, and I did a BFS (I imagine if we are looking for a word with length x, we don't want to look at any word larger than that, but I imagine DFS probably has a very similar speed) I'd love to hear your thoughts let queue = [this.root]; // initialize the queue with the root for (let i = 0; i < word.length; i++) { const newQueue = []; // create a new queue for every letter while (queue.length) { const cur = queue.shift(); if (word[i] === '.') { newQueue.push(...Object.values(cur.children)) // All children can go to the queue if it's a . } else if (word[i] in cur.children) { newQueue.push(cur.children[word[i]]) // otherwise the new queue will be only one element } } if (!newQueue.length) return false; // if the new queue is empty, no paths were found queue = newQueue } return queue.some(node => node.endOfWord) // we will end up with all possible paths from the last point, so we check if any of them are the end of a world

[@Akash0515]

Hey, I encountered "time limit exceeded error" while submitting the code, even after copying your exact code I am still facing the same problem. Can you look over this.

[@BalaguruGupta]

Wow!!! This is the type of learning I was looking for these many days to learn DSA. Thanks much my dear author :)

[@meghanapg7194]

You are the best. Thank you for all the solution videos!

[@ShivamKendre-fc3su]

Very awesome explanation

[@MP-ny3ep]

Awesome explanation as always . Thank you

[@Ryan-sd6os]

how does b.. pass? there is no case that handles that.... maybe you need to add this base case to your solution if i == len(word): return True

[@illu1na]

time complexity for search is missing in this video

[@illu1na]

My guess is O(26**N) for time and O(N) space where N is the max length of the search string

[@lingxu9697]

Yet another amazing video from Neetcode!

[@tonyz2203]

I dont really get the DFS part, how can I improve doing DFS?

[@dodobeebee7352]

Beat TLE by adding a dictionary of previously searched terms, reset dict when word added.

[@mayurakshighosal6499]

what would be the time complexity of this?

[@asr7525]

this code gave me TLE untill i added setrecursionlimit to 10**6 also run time came to be 18257 ms and 17793 ms on each run . but thank you so much for this approach your solutions are always so helpful

[@nikhileswarareddy3182]

This helped, can I know what exactly does this do?

[@ayushsbhatt2751]

@@nikhileswarareddy3182 It increases the recursion limit to 10^6. By default, it is 10^3. Recursion limit is basically the number of recursion call within a recursion call(going deeper).

[@shivambarot9446]

@@nikhileswarareddy3182 import sys sys.setrecursionlimit(10**6)

[@anandkrishnan72]

Is it worth to also implement DP to the backtracking portion of the code when we we have to brute force look through every single node down a certain subtree when we see a period? How would this improve the runtime?

[@shubhamdas6733]

Can you explain how does the search function work when the testcase is "b.."?

[@shaharyar.khalid]

Great explanation! Thank you!

[@ma_sundermeyer]

5.9s/56mb without recursive dfs. DFS is also a neat solution but slower and harder to come up with. I went for an iterative approach, i. e. simply collected a list of pointers to current candidate dicts at every char or ".". For me tries seem to be just glorified nested dicts so I used the latter. Attributes can be simply added as additional keys if needed (better memory as well), such as an "end-of-word" token.

[@AkshayKumar-xh2ob]

Neetcode, I am getting algo expert adds on your video😂

[@rkkasotiya]

You're good at explaining man! Keep up the good work.

[@serenestrolls-d7b]

While implementing it. I didnt see your video but i wrote nearly the same code in Javascript and all the cases passed but the runtime came to 3.5 seconds. which is too big compared to your's time complexity.

[@midhileshmomidi3120]

They had probably added more/complex test cases. Python code is taking like 16 sec

[@ivandrofly]

Thanks :)

[@activelylazy9993]

What is the time complexity of this algo? So in the worst case: such as "...", it would be 26^3 ? so time complexity is 26^(number _of_search_string) ?

[@hungchau]

+1. how do we think about the time complexity for search with the approach presented?

[@xiaonanwang192]

but in your code you don't check the case if '.' is the end of the word and cur.word is True at thei moment

[@fatihmehmetkose]

Thanks!

[@NeetCode]

Thank you so much!!!

[@saurabhdhamnaskar1737]

I tried the above code, but it failed for me against ["a."] This is the entire input - Input ["WordDictionary","addWord","addWord","search","search","search","search","search","search"] [[],["a"],["a"],["."],["a"],["aa"],["a"],[".a"],["a."]] Output [null,null,null,true,true,false,true,false,true] Expected [null,null,null,true,true,false,true,false,false]

[@NhanSleeptight]

You fail to return False for search("a.") so I think you need to return False after visiting every child node for (i + 1)

[@lbvenkatesh]

yep, he forgot to increase the index 'i' in the else part - if you add 'i+=1' after/before line number 33, it works.

[@symbol767]

Damn this one was tricky, thank you man

[@Vancha112]

This was today's problem, but my naive solution ( just using loops) was rated top 10%? :S

[@TheQuancy]

Im not understanding how the dfs will return a boolean if theres no base case

[@studycode4142]

what is the time complexity for this? although that for loop for "." should not increase the complexity in worst case , it is should increase by 26*26, but still wanted to understand if anyone can help please.

[@chloe3337]

for this line: for child in cur.children.values() does child refer to the boolean value or the actual character?

[@tonyz2203]

you can print out to see.

[@roeiamos4491]

it refers to the node representing that character

[@m____s]

I used stack with index. That seems more intuitive def search(self, word: str) -> bool: current_node = self.root stack = [] stack.append([current_node,0]) while stack: #print(stack) current_node, k = stack.pop() if k == len(word): if current_node.end: return True else: continue if word[k] == '.': for chi in current_node.children: stack.append([current_node.children[chi], k+1]) else: if word[k] in current_node.children: stack.append([current_node.children[word[k]], k+1]) return False

[@bishwashkumarsah171]

is not there an extra node with self.children = {} and self.endOfWord = True if for eg:'dad' if i reach the last d and i want to insert it into trie node then cur.children['d'] = trieNode(). ie d:{self.children={},self.endOfWord = True.} Instead of just marking at last 'd' blue i think we need to have a new node whose self.children = {} and self.endOfWord = True

[@jenniferou]

This is great

[@ranjithragul]

few change can beat TLE, atleast now. def search(self, word: str) -> bool: def dfs(i, cur): if i == len(word): return cur.word if word[i] == '.': for k in cur.hashmap.keys(): if dfs(i+1, cur.hashmap[k]): return True return False elif word[i] in cur.hashmap: return dfs(i+1, cur.hashmap[word[i]]) else: return False return dfs(0, self.root)

[@tempomiss8530]

Wow 🙌

[@riyaz3409]

cant we design this same concept as leetcode 208?

[@_PulpoPaul]

What's time complexity?

[@alexli7303]

What if the last character is '.'? When it may not return what you want

[@alexl2512]

I prefer not to mix dfs with for loop. def search(self, word: str) -> bool: def search(node, pos) -> bool: if pos == len(word): return node.isEnd c = word[pos] if c == ".": for child in node.children.values(): if search(child, pos + 1): return True return False else: if c not in node.children: return False else: return search(node.children[c], pos + 1) return search(self.head, 0)

[@asmahamdym]

I don't understand thee 'return cur.word ' part can anyone explain to me??

[@hitman2754]

Please i want morr design question

[@DeGoya]

I did the exact same thing but using BFS and got a time limit exception

[@no3lcodes]

Man, I literally did it like this but I'm guessing my code is a bit wrong in the search function, so I am going to fix it. I'm very happy though because the solution I came up with is literally this, I guess I just need to get better at writing the code or figuring out how to write it. Thanks a lot

[@wtcxdm]

I kept hearing "the end of the world" 😂

[@adityaprasad1322]

17:33 , "we're going down a child" god forbid somebody takes this out of context 💀

[@ananddhakane9534]

TLE!!!

[@jonaskhanwald566]

u forgot Alien dictionary?

[@NeetCode]

Yeah, I noticed the one on lintcode is slightly different than the one on leetcode. I'll probably still do it soon

[@PiyushBajaj05]

Full working and tested code in Java, I found this to be much simpler version: `private static Node root; static class Node { Node[] links = new Node[26]; boolean flag = false; public boolean containsKey(char ch) { return links[ch - 'a'] != null; } public void put(char ch, Node node) { links[ch - 'a'] = node; } public Node get(char ch) { return links[ch - 'a']; } public void setFlag() { flag = true; } } public WordDictionary() { root = new Node(); } public void addWord(String word) { Node node = root; for (int i = 0; i < word.length(); i++) { char currentChar = word.charAt(i); if (!node.containsKey(currentChar)) { node.put(currentChar, new Node()); } node = node.get(currentChar); } node.setFlag(); } public boolean search(String word) { return search_dfs(word, root, 0); } public boolean search_dfs(String word, Node currNode, int startIndex) { for (int i = startIndex; i < word.length(); i++) { char currentChar = word.charAt(i); if (currentChar == '.') { for (Node child : currNode.links) { if (child != null && search_dfs(word, child, i + 1)) { return true; } } return false; } else { if (!currNode.containsKey(currentChar)) { return false; } currNode = currNode.get(currentChar); } } return currNode.flag; }`

[@AbhayNayak]

17:33 - pedo

[@Ynno2]

Doing it iteratively isn't too hard, you just need an explicit stack: def search(self, word: str) -> bool: stack = [(self.root, -1)] while stack: node, depth = stack.pop() if depth == len(word) - 1: if node.isEnd: return True else: continue char = word[depth+1] if char == '.': stack.extend([(child, depth+1) for child in node.children.values()]) elif char in node.children: stack.append((node.children[char], depth+1)) return False

[@Dhruvbala]

The DFS could be written a bit more cleanly -- you don't actually need the for loop def dfs(node, idx): if idx >= len(word): return node.isWord elif word[idx] == '.': for c in node.children: if dfs(node.children[c], idx+1): return True return False else: return ((c:=word[idx]) in node.children) and dfs(node.children[c], idx+1)

[@lokeshnandanwar9203]

Java Code : Beats 61.48 % runtime and 84.03 % Memory class WordDictionary { private Node root; public WordDictionary() { root = new Node(); } public void addWord(String word) { Node node = root; for(int i=0;i

[@mujahirabbasi6270]

I wrote a very simple solution taking advantage of the constraint mentioned that there will be at most 2 dots in word for search queries. It ran in 2595ms. class WordDictionary: def __init__(self): self.wordList = set() def addWord(self, word: str) -> None: self.wordList.add(word) def search(self, word: str) -> bool: search_word = [] # for no "." if "." not in word : search_word.append(word) # for one "." if "." in word : for i in range (97, 123) : newword = word.replace('.', chr(i),1) search_word.append(newword) # for two "." for genwords in search_word : if "." in genwords : for i in range (97, 123) : newgenwords = genwords.replace('.', chr(i),1) search_word.append(newgenwords) # search in data structure for wd in search_word : if wd in self.wordList: return True return False

[@yungboi6902]

Found a python3 solution that resolves the TLE issue: leetcode.com/problems/design-add-and-search-words-data-structure/discuss/2622355/Do-you-have-TLE-Add-this-one-thing-to-your-code!