Implement Trie (Prefix Tree)

Clarify the problem:

• The problem requires us to implement a Trie data structure (also known as a Prefix Tree).
• The Trie should support the following operations:
  • Insert a word into the Trie.
  • Search for a word in the Trie.
  • Check if a given word prefix exists in the Trie.

Analyze the problem:

• Input: Various strings representing words or prefixes.
• Output:
  • For the "insert" operation, there is no output.
  • For the "search" operation, return a boolean indicating whether the word exists in the Trie.
  • For the "startsWith" operation, return a boolean indicating whether any word in the Trie starts with the given prefix.
• Constraints:
  • The input strings consist of lowercase English letters.
  • The total number of words and prefixes inserted is not specified.
  • The Trie should efficiently handle the operations.

Design an algorithm:

• We can implement the Trie using nested dictionaries.
• Each node of the Trie will be represented by a dictionary, where the keys are the characters of the alphabet and the values are the child nodes.
• To insert a word into the Trie, we traverse the Trie from the root node and create new nodes for each character of the word if they don't already exist.
• To search for a word in the Trie, we traverse the Trie from the root node, following the path defined by the characters of the word. If we reach the end of the word and the current node is marked as a word, the word exists in the Trie.
• To check if a given word prefix exists in the Trie, we traverse the Trie from the root node, following the path defined by the characters of the prefix. If we reach the end of the prefix and the current node is not None, there is at least one word in the Trie that starts with the prefix.

Explain your approach:

• We will implement a class called TrieNode to represent the nodes of the Trie.
• Each TrieNode will have a children dictionary to store the child nodes.
• We will also have a boolean attribute is_word to mark the end of a word in the Trie.
• We will implement a class called Trie to encapsulate the Trie operations.
• The Trie class will have a root node representing the root of the Trie.
• We will implement the following methods in the Trie class:
  • insert(word): Inserts a word into the Trie.
  • search(word): Searches for a word in the Trie and returns True if it exists, False otherwise.
  • startsWith(prefix): Checks if a given word prefix exists in the Trie and returns True if it exists, False otherwise.

Write clean and readable code:

python

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


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

    def insert(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_word = True

    def search(self, word):
        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):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Test your code:

python

trie = Trie()
trie.insert("apple")
print(trie.search("apple"))      # Output: True
print(trie.search("app"))        # Output: False
print(trie.startsWith("app"))    # Output: True
trie.insert("app")
print(trie.search("app"))        # Output: True

Explanation:

• We insert the word "apple" into the Trie and then perform search and prefix checks.
• The word "apple" exists in the Trie, so search("apple") returns True.
• The word "app" does not exist in the Trie, so search("app") returns False.
• There is at least one word in the Trie that starts with the prefix "app", so startsWith("app") returns True.
• We insert the word "app" into the Trie and then search for it, which returns True.

Optimize if necessary:

• The Trie implementation provided is already optimized and efficient for the given operations.

Handle error cases:

• The code assumes that the input follows the problem constraints. It does not explicitly handle invalid input cases.

Discuss complexity analysis:

• Let N be the average length of the words/prefixes inserted into the Trie.
• The space complexity of the Trie is O(N) since it stores each character of the words/prefixes.
• The time complexity of the insert, search, and startsWith operations is O(N) in the worst case, where N is the length of the word/prefix. This is because we traverse the Trie character by character.
• The solution provides an efficient way to store and search for words and prefixes in the Trie.