DSA: Tries

Tandid Alam
Nov 27, 2022
1 min read

Updated: Nov 28, 2022

Fundamentals of Tries

Basic Implementation

Practice Problems

Learning Resources

Fundamentals of Tries

This data structure is constructed from strings and generates a tree based on the characters of the string. We start from the leftmost character and connect each of the new characters as a node of the tree. The graphic shows the basic idea of insertion and what our data structure would look like.

Basic Implementation

 class Node:
    def __init__(self, val):
        self.value = val
        self.children = {}

    def insert(self, s, idx):
        # idx: index of the current character in s
        if idx != len(s):
            
            char = s[idx]
            self.children.setdefault(char, Node(char))
            self.children.get(char).insert(s, idx + 1)
            
    def query(self):
        # Some code goes here 
        ...
                      
def create_trie(words):
    trie = Node('$')
    for word in words:
        trie.insert(word, 0)
    return trie

Practice Problems

Autocomplete

Problem:

For this question, we first give you a series of n words. For every word, we first add it to our dictionary, and then we type out the word using the minimum number of strokes to autocomplete the word. What is the minimum total number of strokes needed to type out all the words?

Example:

Input 1: words = ["hi", "hello", "bojack", "hills", "hill"]

Output 1: 11

Solution:

class Node: 
    def __init__(self, val):
    #  Add freq to keep track of frequency we get this prefix
        self.value = val
        self.children = {}
        freq = 0
    
    def insert(self, s, idx):
        self.freq += 1

        if len(s) != idx:
            char = s[idx]
            self.children.setdefault(char, Node(char))
            self.children.get(char.insert(s, idx + 1))

    def query(self, s, idx):
      # We have reached end of prefix, terminate by returning 0
        if len(s) == idx or self.freq == 1:
            return 0
        
        char = s[idx]
        return self.children.get(char).query(s, idx + 1) + 1

def autocomplete(words):
    trie = Node('$')
    total = 0

    for word in words: 
        trie.insert(word, 0)

        total = total + trie.query(word, 0)
    # Adding + 1 eliminates the implementation inconsistency
    return total + 1

Prefix Count

Problem:

Given a dictionary, containing a list of words, and a list of queries, which consists of a list of prefixes, compute the result of each query. Each query is simply a string denoting a prefix. For each query, return the number of words in the dictionary that contains that prefix.

Only lower-case English letters will be used.

Example:

Input: words = ["forgot", "for", "algomonster", "while"], prefixes = ["fo", "forg", "algo"]

Output: [2, 1, 1]

Solution:

class Node:
  # Add freq to keep track of frequency we get this prefix
  def __init__(self, value):
      self.value = value
      self.freq = 0
      self.children = {}

  def insert(self, s, idx):
      self.freq += 1
      if idx != len(s):
          char = s[idx]
          self.children.setdefault(s[idx], Node(s[idx]))
          self.children.get(s[idx]).insert(s, idx + 1)

  def prefix_check(self, s, idx):
      # we have reached end of prefix, end by returning the value
      if len(s) == idx:
          return self.freq
          
      # go to the children if it exists
      char = s[idx]
      if char in self.children:
          return self.children.get(s[idx]).prefix_check(s, idx + 1)
      
      # if character not in children, dictionary doesn't have prefix
      else:
          return 0

def prefix_count(words, prefixes):
    trie = Node('$')
    for word in words:
        trie.insert(word, 0)
    ans = []
    for prefix in prefixes:
        ans.append(trie.prefix_check(prefix, 0))
    return ans