208.Implement Trie (Prefix Tree)

Tags: [tree], [trie], [prefix_tree], [prefix], [search], [data_structure]

Com: {fb}

Link: https://leetcode.com/problems/implement-trie-prefix-tree/\#/description

Implement a trie withinsert,search, andstartsWithmethods.

Note:
You may assume that all inputs are consist of lowercase lettersa-z.

Solution:

class Trie(object):

    class TrieNode(object):
        def __init__(self, val):
            self.val = val
            self.end_of_word = False
            self.children = []


    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = self.TrieNode('')


    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        self.insert_helper(self.root, word, 0)


    def insert_helper(self, root, word, index):
        curr = word[index]
        target_node = None
        for child in root.children:
            if child.val == curr:
                target_node = child
                break

        if not target_node:
            target_node = self.TrieNode(curr)
            root.children.append(target_node)

        if index == len(word) - 1:
            target_node.end_of_word = True
            return

        self.insert_helper(target_node, word, index + 1)


    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        if not word:
            return False

        return self.search_helper(self.root, word, 0)


    def search_helper(self, root, word, index):
        curr = word[index]
        for child in root.children:
            if child.val != curr:
                continue

            if index == len(word) - 1:
                return child.end_of_word

            return self.search_helper(child, word, index + 1)

        return False


    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        if not prefix:
            return False

        return self.starts_with_helper(self.root, prefix, 0)


    def starts_with_helper(self, root, prefix, index):
        # base case
        if index >= len(prefix):
            return True

        curr = prefix[index]
        for child in root.children:
            if child.val != curr:
                continue

            return self.starts_with_helper(child, prefix, index + 1)

        return False


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Revelation:

• After generating a new node, need append this node into the root.children.

Note:

• Time complexity of initialization = O(1).
• Time complexity of insert = O(n), n is the length of the word.
• Time complexity of search = O(n), n is the length of the word.
• Time complexity of startsWith = O(n), n is the length of the word.