Trie

Because of trie’s implementation is long, we need to use DFS to traverse to find some keys among all keys. It is not often asked in the interview. Here we will only show some basic knowledge.

What is Trie?

Trie is originated from retrieve. It is also know as digital tree or prefix tree. It is a type of search tree, a tree data structure used for locating specific keys from within a set.

Trie has following properties,

• Root node doesn’t contain characters.
• A complete key is composed of all characters traversed from root to the current position.
• Each node’s all sub nodes are different.

Trie vs Hash Table:

A trie can be used to replace a hash table. Here we will compare the trie with hash table.

Hash table’s worst case time complexity is O(n) when we need to rehashing the whole table. Trie’s time worst time complexity is same as its average time complexity, which is O(m) m is the length of a key, which is also the average complexity of hash table.

Hash table’s space usage will be more than trie’s when there are many repeated prefix keys.

When to use trie?

• Finding all keys with a common prefix.
• Enumerating a dataset of strings in lexicographical order.

Template:

There are two ways to implement a trie.

• A general way is using a hash map.

  • The main structure is a TreeNode class containing a hash map. The hash map contains next level’s prefixes as keys and TreeNode as values.
  • If we have both searchKeyand searchPrefixfunctions, we need to add one more property of boolean isFinal. The isFinal property of a node can tell the difference between a prefix and a whole key.
  • A pit fall of this data structure is we don’t need to save each TreeNode key inside each node because not all TreeNode have keys. A root TreeNodedoesn’t have a key.

  class Trie {
    
      TrieNode root;
        
      public Trie() {
          root = new TrieNode();
      }
        
      public void insert(String word) {
            
          TrieNode cur = root;
          char[] wordChars = word.toCharArray();
          for(char c : wordChars) {
                
              if(cur.children.containsKey(c)) {
                  cur = cur.children.get(c);
                  continue;
              }
                
              TrieNode newNode = new TrieNode();
              cur.children.put(c, newNode);
              cur = newNode;
          }
            
          cur.isFinal = true;
            
      }
        
      public boolean search(String word) {
            
          TrieNode cur = root;
          char[] wordChars = word.toCharArray();
          for(char c :wordChars) {
              if(!cur.children.containsKey(c)) {
                  return false;
              }
              cur = cur.children.get(c);
                
          }
            
          if(cur.isFinal) {
              return true;
          }
          return false;
      }
        
      public boolean startsWith(String prefix) {
          TrieNode cur = root;
          char[] prefixChars = prefix.toCharArray();
            
          for(char c :prefixChars) {
              if(!cur.children.containsKey(c)) {
                  return false;
              }
              cur = cur.children.get(c);
                
          }
            
          return true;
            
      }
  }
    
  class TrieNode {
      boolean isFinal;
      Map<Character, TrieNode> children;
        
      TrieNode() {
          isFinal = false;
          children = new HashMap<>();
      }
  }
  

• If a key only contains letters, we can also use array whose length is 26.

  class Trie {
      class TrieNode{
          TrieNode[] children;
          boolean istail;//记录是否是某个单词的末尾
          public TrieNode(){
              this.children = new TrieNode[26];
              this.istail=false;
          }
      }
      public TrieNode root;
      public Trie(){
          this.root = new TrieNode();
      }
      public void insert(String word){
          TrieNode node = this.root;
          for(int i = 0 ;i < word.length();i++){
              if(node.children[word.charAt(i)-'a'] == null){//如果有这个字母
                  node.children[word.charAt(i)-'a'] = new TrieNode();
              }
              node = node.children[word.charAt(i)-'a'];
          }
          node.istail=true;
      }
      public boolean search(String word){
          TrieNode node = this.root;
          for(int i = 0 ;i < word.length();i++){
              if(node.children[word.charAt(i)-'a']==null){//如果没有这个字母
                  return false;
              }
              else {
                  node = node.children[word.charAt(i)-'a'];
              }
          }
          if(node.istail) return true;
          else return false;
      }
      public boolean startsWith(String prefix){
          TrieNode node = this.root;
          for(int i = 0 ;i < prefix.length();i++){
              if(node.children[prefix.charAt(i)-'a']==null){//如果没有这个字母
                  return false;
              }
              else {
                  node = node.children[prefix.charAt(i)-'a'];
              }
          }
          return true;
      }
  }
  

Problems

588. Design In-Memory File System

212. Word Search II

642. Design Search Autocomplete System

336. Palindrome Pairs