Implement a Trie Data Structure for Efficient Prefix Searching in Python

A Trie (pronounced as “try”) is a tree-like data structure that is commonly used for storing strings. It is particularly useful for efficient prefix searching, as it allows for quick lookups, insertions, and deletions.

Implementation of a Trie in Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_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_end_of_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_end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# Example usage
def main():
    trie = Trie()
    
    # Insert words into the Trie
    words = ["hello", "world", "hi", "her", "hero", "heron", "he"]
    for word in words:
        trie.insert(word)

    # Search for words
    print(trie.search("hero"))  # True
    print(trie.search("her"))   # True
    print(trie.search("hey"))   # False

    # Check prefixes
    print(trie.starts_with("he"))  # True
    print(trie.starts_with("wo"))  # True
    print(trie.starts_with("ha"))  # False

if __name__ == "__main__":
    main()

Explanation:

1. TrieNode Class:
   • Each node in the Trie is represented by an instance of TrieNode.
   • children: A dictionary where the keys are characters, and the values are TrieNode instances representing the next node in the Trie.
   • is_end_of_word: A boolean flag that indicates if a node represents the end of a word.
2. Trie Class:
   • Insert Method:
     • Inserts a word into the Trie by iterating through its characters.
     • If a character is not present in the current node’s children, a new TrieNode is created.
     • The is_end_of_word flag is set to True at the last character node of the word.
   • Search Method:
     • Searches for a word in the Trie.
     • If all characters are found in sequence and the final node’s is_end_of_word flag is True, the word exists in the Trie.
   • Starts With Method:
     • Checks if there is any word in the Trie that starts with the given prefix.
     • It returns True if all characters of the prefix are found in sequence; otherwise, it returns False.

Example Output:
True
True
False
True
True
False

Use Cases:

• Prefix Searching: Quickly find if a prefix exists in a large set of words, useful in applications like auto-complete, spell-checkers, and search engines.
• Efficient Storage: Tries efficiently store strings by sharing common prefixes, which can save memory when storing large dictionaries.

This implementation provides a basic structure that can be expanded to handle more advanced operations such as word deletion, finding all words with a given prefix, and more.