Implement Trie (Prefix Tree)

# Implement Trie (Prefix Tree) ## Difficulty Medium ## Tags `trie`, `design`, `data structure` ## Problem Statement Implement a Trie (prefix tree) with the following operations: - `insert(word)`: Inserts the string `word` into the trie. - `search(word)`: Returns `True` if the string `word` is in the trie. - `starts_with(prefix)`: Returns `True` if there is any word in the trie that starts with `prefix`. ## Constraints - 1 ≤ word.length, prefix.length ≤ 2000 - `word` and `prefix` consist only of lowercase English letters. - At most 3 × 10⁴ calls in total to insert, search, and starts_with. ## Signatures ### Python ```python class Trie: def insert(self, word: str) -> None: pass def search(self, word: str) -> bool: pass def starts_with(self, prefix: str) -> bool: pass ``` ### Java ```java public class Trie { // Implement methods here } ``` ### Csharp ```csharp public class Trie { // Implement methods here } ``` ### Cpp ```cpp class Trie { public: // Implement methods here }; ``` ### C ```c void __init__() { } ``` ### Ruby ```ruby def __init__() end ``` ### Perl ```perl sub __init__ { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def __init__(): Unit = { } } ``` ### Haskell ```haskell __init__ :: ... -> ... __init__ args = undefined ``` ### Clojure ```clojure (defn __init__ [] ) ``` ### Scheme ```scheme (define (__init__ ) ) ``` ## Examples ### Example 1 **Input:** ``` trie = Trie() trie.insert("apple") trie.search("apple") # returns True trie.search("app") # returns False trie.starts_with("app") # returns True trie.insert("app") trie.search("app") # returns True ``` **Output:** ``` True, False, True, True ``` ### Example 2 **Input:** ``` trie = Trie() trie.insert("hello") trie.insert("help") trie.starts_with("hel") # True trie.search("hel") # False trie.search("hello") # True ``` ## Hints 1. Each node has a dictionary/array of children (size 26 for lowercase letters). 2. Each node has a boolean `is_end_of_word` flag. 3. For `insert`: traverse/create nodes for each character, mark end. 4. For `search`: traverse nodes, return True only if path exists AND ends at `is_end_of_word = True`. 5. For `starts_with`: traverse nodes, return True if path exists (regardless of end flag).