Design Add and Search Words Data Structure
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Build addWord(word) and search(word), where search may contain '.' that matches any one letter.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Without '.', a search follows exactly one path. What changes at a '.'?
- Hint 2Use recursion: at a '.', succeed if ANY child succeeds.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
The same phone-book tabs, but your search note has a blank: ".ad". At the blank you cannot pick one tab, so you open every tab at that level and continue the rest ("ad") in each. If any tab leads to a red sticker after the last letter, the search succeeds.
- The obvious way
Store words in a list and compare each against the pattern: O(words x length).
- The key insight
addWord is the normal trie insert. search(word) recurses with (node, position): at the end of the word return node.is_word; for a normal letter follow that child (fail if missing); for '.' try every child and return True if any works.
- The algorithm
- addWord: standard trie insertion.
- search: match(node, position).
- Letter: follow its child. '.': try every child.
- At the end return the node's word flag.
Watch it run
Exampleadd bad, dad, mad; search pad, bad, .ad, b..
After adding bad, dad, mad the first tabs are b, d, m, each followed by a, d.
tabs: b, d, m
Where people slip
- Do not forget to check the word flag at the very end, otherwise "ba" would match "bad".
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
class WordDictionary:
def __init__(self):
self.children = {}
self.is_word = False
def addWord(self, word):
node = self
for letter in word:
if letter not in node.children:
node.children[letter] = WordDictionary()
node = node.children[letter]
node.is_word = True
def search(self, word):
def match(node, position):
if position == len(word):
return node.is_word
letter = word[position]
if letter == ".": # the blank: open every tab at this level
return any(match(child, position + 1) for child in node.children.values())
child = node.children.get(letter)
return child is not None and match(child, position + 1)
return match(self, 0)Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.