Trie - How to Succeed in Algorithms Interview


Trie - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series


Applications of Trie

  • Trie for words, numbers(each digit), bit
  • prefix: findByPrefix
  • list of strings, dictionary
  • Use trie to prune

Advantages

  • Less space
  • Avoid unnecessary computation with same prefixes

Complexity

  • time/space complexity: sum of all word length

Operations on Trie

  • insert + query

Augmented Trie

  • left/rightCnt, dupCnt, subTreeCnt
  • count of prefix nodes: curr.child[c].count++;
  • store word at last node
  • isEnd

Trie

private boolean dfs(int curId, String word, Node parentPtr, int cntMismatched) {
    if (cntMismatched > 1) {
        return false;
    }
    if (curId == word.length()) {       
        return parentPtr.isWordEnd && cntMismatched == 1;
    }
    for (int i = 0; i < 26; i++) {          
        int order = word.charAt(curId) - 'a';
        if (parentPtr.children[i] == null)
            continue;       
        if (order != i) {
            if (dfs(curId + 1, word, parentPtr.children[i], cntMismatched + 1))
                return true;
        } else {
            if (dfs(curId + 1, word, parentPtr.children[i], cntMismatched))
                return true;
        }
    }     
    return false;
}
  • LeetCode 472 - Concatenated Words
    • Given a list of words, please write a program that returns all concatenated words in the given list of words.
    public boolean testWord(char[] chars, int index, TrieNode root, int count) { // count means how many words during the search path
      TrieNode cur = root;
      int n = chars.length;
      for (int i = index; i < n; i++) {
          if (cur.sons[chars[i] - 'a'] == null) {
              return false;
          }
          if (cur.sons[chars[i] - 'a'].isEnd) {
              if (i == n - 1) { // no next word, so test count to get result.
                  return count >= 1;
              }
              if (testWord(chars, i + 1, root, count + 1)) {
                  return true;
              }
          }
          cur = cur.sons[chars[i] - 'a'];
      }
      return false;
    }

Trie + BFS

Bit Trie

Prefix Xors + Bit Trie

Suffix Trie

Generalized Suffix Tree

Examples

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9]. (order does not matter).

Trie implementation

class TrieNode {  
    public TrieNode[] children = new TrieNode[26];  
    public String item = "";        
    public TrieNode() {  
    }  
}  
class Trie {  
    private TrieNode root;  
    public Trie() {  
        root = new TrieNode();  
    }  
    // Inserts a word into the trie.  
    public void insert(String word) {  
        TrieNode node = root;  
        for (char c : word.toCharArray()) {  
            if (node.children[c - 'a'] == null) {  
                node.children[c - 'a'] = new TrieNode();  
            }  
            node = node.children[c - 'a'];  
        }  
        node.item = word;  
    }  
    // Returns if the word is in the trie.  
    public boolean search(String word) {  
        TrieNode node = root;  
        for (char c : word.toCharArray()) {  
            if (node.children[c - 'a'] == null) return false;  
            node = node.children[c - 'a'];  
        }  
        return node.item.equals(word);  
    }  
    // Returns if there is any word in the trie  
    // that starts with the given prefix.  
    public boolean startsWith(String prefix) {  
        TrieNode node = root;  
        for (char c : prefix.toCharArray()) {  
            if (node.children[c - 'a'] == null) return false;  
            node = node.children[c - 'a'];  
        }  
        return true;  
    }  
}  

Resources

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)