Implement Trie (Prefix Tree)

Problem

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Intuition

The task is to design a data structure that supports adding new words and finding if a string matches any previously added string. The key challenge is to handle wildcard characters (dots) in the search queries, where dots can match any letter. To achieve this, we can use a Trie (prefix tree) data structure, where each node represents a character in a word.

Approach

Trie Node:

Implement a TrieNode class with attributes:
children: A dictionary mapping characters to child nodes.
is_end_of_word: A boolean indicating whether the current node marks the end of a word.
WordDictionary Class:

Implement a WordDictionary class with methods:
init: Initializes an empty Trie with a root node.
addWord: Inserts a word into the Trie by iterating over its characters and creating nodes as needed. The last node of the word is marked as the end of a word.
search: Searches for a word in the Trie, handling wildcard characters. Recursively explores all possible paths in the Trie for wildcard characters.
Insertion:

During insertion, iterate over each character of the word.
If the character is not already a child of the current node, create a new child node.
Move to the next node and repeat the process until all characters are inserted. Mark the last node as the end of a word.
Search:

During search, iterate over each character of the word.
If a character is a wildcard ('.'), explore all possible paths by recursively searching the Trie for the remaining characters.
If a character is not a wildcard, check if it is a child of the current node.
Return True only if the end of a valid word is reached.

Complexity

• Time complexity:

Insertion: The time complexity of insertion is O(m), where m is the length of the word being inserted.
Search: The time complexity of search depends on the number of wildcard characters in the query. In the worst case, where there are k wildcard characters, the time complexity is O(26^k * m), where m is the length of the word.

• Space complexity:

The space complexity of the Trie depends on the number of unique words and the length of the words. In the worst case, where there are no common prefixes among the words, the space complexity is O(n * m), where n is the number of words and m is the average length of the words. The space complexity is dominated by the Trie structure.

Code

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

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

    def addWord(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        return self._search_word(self.root, word)

    def _search_word(self, node, word):
        for i, char in enumerate(word):
            if char == '.':
                for child in node.children.values():
                    if self._search_word(child, word[i + 1:]):
                        return True
                return False
            elif char not in node.children:
                return False
            node = node.children[char]

        return node.is_end_of_word