algoadvance

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 spell checker.

Implement a Trie with the following methods:

• 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 that has the prefix prefix, and false otherwise.

Clarifying Questions

1. Case Sensitivity: Should the trie treat “Apple” and “apple” as different strings?
   • Let’s assume case-sensitivity is respected (this needs to be confirmed if in a real scenario).
2. Characters Allowed: Should we only consider lowercase English letters for simplicity?
   • Yes, for simplicity we will only consider lowercase English letters.
3. Consecutive Inserts and Searches: Can we assume that the methods will be called multiple times and independently?
   • Yes, the methods can be called in any sequence.

Strategy

Trie Node

• Each node in the Trie will contain:
  • A dictionary children where each key is a character and the value is another Trie node.
  • A boolean is_word to mark the end of a word.

Trie

• Initialize: Create the root node (an empty Trie node).
• Insert: Traverse the Trie based on characters of the word; create new nodes as necessary and mark the end of the word.
• Search: Traverse the Trie based on characters of the word; ensure all characters exist and the final node is marked as a word.
• StartsWith: Like search, but only verify the existence of the characters without needing to check the is_word flag.

Code

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

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

Time Complexity

• Insert: O(n) where n is the length of the word to insert.
• Search: O(n) where n is the length of the word to search.
• StartsWith: O(n) where n is the length of the prefix.

Here, creating/traversing nodes takes linear time with respect to the length of the word or prefix being processed.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?