Design Add and Search Words Data Structure

Problem Summary

• Build a data structure that supports adding words and searching for words with . as placeholders.
• Like regex . could match with anything

What is Being Asked?

• Build a Trie then implement search() where . matches with any available letters

Key Observations

• Having TrieNode().children a Hash Map would allow us to iterate through each letter at that level with just currentNode.children.keys()

Main Concepts Used

• Trie
• Hash Map
• Recursion

Time & Space Complexity

Time:

• init() -> $O(1)$
• addWord(word) -> worst case $O(len(word))$
• search(word) -> worse case $O(n)$ where n is all characters in the Trie

Space:

• init() -> $O(1)$
• addWord(word) -> $O(len(word))$
• search(word) -> $O(n)$ for the recursive call stack

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False


class WordDictionary:

    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        cur = self.root

        for letter in word:
            if letter not in cur.children:
                cur.children[letter] = TrieNode()
            cur = cur.children[letter]
        cur.isEndOfWord = True

    def search(self, word: str) -> bool:
        return self.searchHelper(word, self.root)

    def searchHelper(self, word: str, root: TrieNode) -> bool:
        for i, letter in enumerate(word):
            if letter == ".": 
                # special case where we need to go down each route
                for potentialLetter in root.children.keys():
                    isFound = self.searchHelper(word[i+1:], root.children[potentialLetter])
                    if isFound:
                        return True
                return False

            if letter not in root.children:
                return False
            root = root.children[letter]
        return root.isEndOfWord

Common Mistakes / Things I Got Stuck On

• Using main function instead of helper function for recursion
• Not reading the full question and thinking its a duplicate of Implement Trie Prefix Tree
• Implementing the TrieNode().children using Array instead of Hash Map