Problem Statement in English

You’ve to design a data structure that supports the following operations:

  • addWord(word: str): Adds a word to the data structure.
  • search(word: str): Returns True if the word is in the data structure, and False otherwise. The word may contain dots '.' which represent any letter (a wildcard operator essentially).

Approach

This problem is easily solved with a Trie. If you’re new to Tries, check out this problem.

We can use a Trie to store the words and then search for them. The only catch is that we need to be able to search for words with a “.” in them. This is a wildcard character that can match any character.

This requires us to do a depth-first search on the Trie. We can do this recursively. I think it’ll make more sense if we just jump into the code.

Solution in Python


# Definition for a trie node.
class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.isTerminal = False


class WordDictionary:

    def __init__(self):
        # Initialize the root of the Trie
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        # set the pointer to the root of the Trie
        ptr = self.root

        # for each character in the word
        for char in word:
            # if the character is not in the children of the `TrieNode`
            if char not in ptr.children:
                # add the character to the children of the `TrieNode`
                # as a new `TrieNode`
                ptr.children[char] = TrieNode()

            # move the pointer to the child `TrieNode`
            ptr = ptr.children[char]

        # set the `isTerminal` on the the `TrieNode`
        # flag to True
        ptr.isTerminal = True

    def search(self, word: str) -> bool:
        # flag to indicate if the word was found
        wasFound = False

        def recursiveCall(pointer: TrieNode, charIndex: int):
            # bind this variable to the enclosing scope
            nonlocal wasFound

            # if the word was found, return
            # since we don't care about the rest anymore
            if wasFound:
                return

            # if we're looking for the 
            # last character of the word
            if charIndex == len(word) - 1:
                # if the character is in the children of the `TrieNode`
                if not wasFound and word[charIndex] in pointer.children:
                    # set the flag to the `isTerminal` of the child
                    wasFound = pointer.children[word[charIndex]].isTerminal
                # if the character is a wildcard
                # and the word is not found yet
                elif not wasFound and word[charIndex] == ".":
                    flag = False

                    # check if any of the children are terminal
                    for child in pointer.children.values():
                        # if a child is terminal
                        if child.isTerminal:
                            # set the flag to `True`
                            flag = True
                            break

                    # set the answer to be the flag
                    wasFound = flag

            # if the character exists in the children of the `TrieNode`
            elif word[charIndex] in pointer.children:
                # check for the next character 
                # in the word we're searching for
                recursiveCall(pointer.children[word[charIndex]], charIndex + 1)

            # if the character is a wildcard
            elif word[charIndex] == ".":
                # check for the next character index
                # in all the children of the current `TrieNode`
                for childTrieNode in pointer.children.values():
                    recursiveCall(childTrieNode, charIndex + 1)

        # start the recursive call
        recursiveCall(self.root, 0)

        # return the answer
        return wasFound

Complexity

  • Time:

    • addWord: $O(n)$
      Since we insert $n$ characters at most in the Trie.
    • search: $O(n)$
      Since we search through $n$ characters at most in the Trie.

  • Space: $O(n)$
    Since we store $n$ characters in the Trie, where $n$ is the length of the word.

Mistakes I Made

I needed a nudge to realise I could use DFS to implement wildcard search. I was initially trying to copy the children of the current Trie node everytime I encountered a wildcard character. This was unnecessary and made the code more complex than it needed to be.

And we are done.