Implement Trie (Prefix Tree) medium

Problem Statement

Implement a Trie (Prefix Tree).

A trie is a tree-like data structure used for efficient retrieval of keys in a set of strings. Nodes in a trie contain a map of children, with each child representing a character. Each path from the root to a node represents a prefix, and each path ending at a node marked as a "word" represents a complete word.

Implement the Trie class:

• Trie(): Initializes the trie object.
• insert(word): Inserts the string word into the trie.
• search(word): Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• startsWith(prefix): Returns true if there is a previously inserted string word that starts with the given 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

Example 2

Input
["Trie", "insert", "search", "startsWith", "insert", "search"]
[[], ["a"], ["a"], ["a"], ["b"], ["a"]]
Output
[null,null,true,true,null,true]

Steps

1. Node Class: Create a class TrieNode to represent each node in the trie. Each node will have a dictionary (children) to store its children (keyed by character) and a boolean flag (is_word) to indicate if the node represents the end of a word.

2. Trie Class: Create the Trie class with the insert, search, and startsWith methods.

3. insert(word): Traverse the trie, adding nodes as needed for each character in the word. Set is_word to True for the last node.

4. search(word): Traverse the trie. If a node is not found for a character, return False. If the traversal reaches the end of the word and is_word is True, return True.

5. startsWith(prefix): Similar to search, but it only needs to check if the prefix exists. It doesn't need to check is_word.

Explanation

The Trie data structure is optimized for prefix-based searches. By organizing words in a tree based on their prefixes, we avoid redundant comparisons. The insert operation has a time complexity proportional to the length of the word, as we traverse the tree character by character. The search and startsWith operations similarly have a time complexity proportional to the length of the word or prefix. Space complexity depends on the number of words and their lengths, but it can be significantly more efficient than other string searching techniques for many cases.

Code

class TrieNode:
    def __init__(self):
        self.children = {}  # Dictionary to store children nodes
        self.is_word = False  # Flag to indicate end of word


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

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_word

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Complexity

• Time complexity:

  • insert: O(m), where m is the length of the word.
  • search: O(m), where m is the length of the word.
  • startsWith: O(m), where m is the length of the prefix.

• Space complexity: O(N*M), where N is the number of words inserted, and M is the maximum length of a word. This is because we store all the characters of all the inserted words in the Trie.