Leo-20180715.md

Leo Lei | 雷雨

July 15, 2018

1.Leetcode

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Analysis

Essentially, an trie is a special kind of a tree.

There are many ways to represent an trie node. For example, we may use a 26-slots list, each slot for a character, assuming only lower-case strings will be stored. In each slot, we need to preserve information like whether the slot contains a value (Boolean) - if it does, whether it's the terminal character(e.g. "e" in "apple"); if not, we need an pointer pointing to the next node. A data structure for a single node would be [[has_value, is_terminal, next_node] for _ in range(26)]. It's quick to access a specific slot in a list, but we will end up wasting lots of memory cause we only use a small portion of the slots.

Another way is using dict or hash table to represent a node. In each node, we map characters to their next level nodes. Also, we need to know if a character terminates the string. In this way, we use memory only when it's necessary. Below is an implementation of this approach.

Implementation

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        # a dict mappping char to its children which are tries themselves
        self.tries = {}  


    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        tries = self.tries
        for c in word:
            if c not in tries:
                tries[c] = {}
            tries = tries[c]
        tries['END'] = 'END'


    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        tries = self.tries
        for c in word:
            if c not in tries:
                return False
            tries = tries[c]
        return 'END' in tries


    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        """
        tries = self.tries
        for c in prefix:
            if c not in tries:
                return False
            tries = tries[c]

        return True

# 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)

2. Article and comment

Implement Trie (Prefix Tree) - Solution

It's the official solution for the problem above. It provides some interesting uses of the trie structure. Also, it visualizes the problem and give some sample codes.

3. New skill

TODO

4. Share an article

Lessons from releasing a personal project as a commercial product

Learn how to build a commercial product from the scratch (or a side project).