LeetCode #208: Implement Trie (Prefix Tree)

https://leetcode.com/problems/implement-trie-prefix-tree/

The problem requires implementing a Trie data structure, also known as a Prefix Tree, which allows for efficient insertion, deletion, and searching of words. A Trie is a tree-like data structure that stores a set of strings, where each node represents a prefix of the strings stored in the tree.

Algorithm:

1. Define a TrieNode class that has a dictionary to store child nodes, and a boolean to indicate if the node represents the end of a word.
2. Define a Trie class that has a root node and the following methods:
3. insert: Takes in a string and inserts it into the trie.
4. Start at the root node and iterate over the characters in the string.
5. For each character, check if the current node has a child node with that character. If it does not, create a new child node and add it to the current node’s dictionary with the character as the key.
6. Move to the child node and continue iterating over the remaining characters in the string.
7. After iterating over all the characters, set the boolean value of the final node to True to indicate that it represents the end of a word.
8. search: Takes in a string and returns True if the string is in the trie and False otherwise.
9. Start at the root node and iterate over the characters in the string.
10. For each character, check if the current node has a child node with that character. If it does not, the string is not in the trie, and we return False.
11. Move to the child node and continue iterating over the remaining characters in the string.
12. After iterating over all the characters, check if the final node has a boolean value of True. If it does, the string is in the trie, and we return True. Otherwise, the string is not in the trie, and we return False.
13. startsWith: Takes in a string and returns True if there is any word in the trie that starts with the given prefix, and False otherwise.
14. Start at the root node and iterate over the characters in the prefix.
15. For each character, check if the current node has a child node with that character. If it does not, the prefix is not in the trie, and we return False.
16. Move to the child node and continue iterating over the remaining characters in the prefix.
17. After iterating over all the characters, the prefix is in the trie, and we return True.

Python Solution:

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:
        current = self.root
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.is_word = True

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

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

We start by defining a TrieNode class that has a dictionary to store child nodes and a boolean to indicate if the node represents the end of a word. Then, we define a Trie class that has a root node and the following methods: insert, search, and startsWith. The insert method takes in a string and inserts it into the trie, while the search method takes in a string and returns True if the string is in the trie and False otherwise. Finally, the startsWith method takes in a string and returns True if there is any word in the trie that starts with the given prefix.

Time and Space Complexity

The time complexity of inserting, searching, and prefix searching in the trie is O(m), where m is the length of the string. This is because we need to iterate over each character in the string to traverse the tree. The space complexity of the trie depends on the number of strings inserted into the trie and the length of those strings. In the worst case, where all the inserted strings have no common prefixes, the space complexity of the trie is O(n*m), where n is the number of strings and m is the maximum length of the strings. However, in practice, the space complexity is usually much lower than this worst-case scenario since many strings have common prefixes, resulting in a shared prefix tree.