Implement Trie (Prefix Tree) medium

Problem Statement

Implement a Trie (Prefix Tree) data structure.

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 mapping from characters to child nodes. Each path from the root to a leaf represents a word in the Trie.

Implement the Trie class:

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

Output [null, null, true, true, false]

Steps

1. Trie Node Structure: Design a node structure to represent a node in the Trie. It should contain:

   • A boolean flag isWord indicating whether this node represents the end of a word.
   • A dictionary (or hash map) children to store child nodes, mapping characters to their corresponding nodes.

2. insert(word): Iterate through the characters of the input word. For each character:

   • If a child node for that character exists, move to that child.
   • Otherwise, create a new child node and move to it.
   • Once the entire word is processed, mark the last node as isWord = true.

3. search(word): Similar to insert, iterate through the characters of the input word. If at any point a child node for a character is not found, return false. If the entire word is processed, return true only if the last node's isWord flag is true.

4. startsWith(prefix): Similar to search, but you don't need to check the isWord flag at the end. Return true if you reach the end of the prefix without encountering a missing child node.

Explanation

The Trie data structure efficiently stores strings and allows for fast prefix searches. The key is that the common prefixes are shared among different words. This reduces space compared to storing each word independently, especially when there are many words with common prefixes. The time complexity for insertion, search, and startsWith operations is proportional to the length of the string, making it very efficient for autocompletion and other prefix-based operations.

Code

public class Trie {
    private class TrieNode {
        public bool isWord;
        public Dictionary<char, TrieNode> children;

        public TrieNode() {
            isWord = false;
            children = new Dictionary<char, TrieNode>();
        }
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void Insert(string word) {
        TrieNode node = root;
        foreach (char c in word) {
            if (!node.children.ContainsKey(c)) {
                node.children[c] = new TrieNode();
            }
            node = node.children[c];
        }
        node.isWord = true;
    }

    public bool Search(string word) {
        TrieNode node = root;
        foreach (char c in word) {
            if (!node.children.ContainsKey(c)) {
                return false;
            }
            node = node.children[c];
        }
        return node.isWord;
    }

    public bool StartsWith(string prefix) {
        TrieNode node = root;
        foreach (char c in prefix) {
            if (!node.children.ContainsKey(c)) {
                return false;
            }
            node = node.children[c];
        }
        return true;
    }
}

Complexity

• Time Complexity:

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

• Space Complexity: O(N*M), where N is the number of words inserted, and M is the maximum length of a word. In the worst case (all words are unique and have no common prefixes), the space used will be proportional to the total number of characters in all inserted words.