Session 36: Tries

Original Session

Date: 01 Feb 2025

Topic: Tries

Concept: Asked by Microsoft, Google
Tree-like data structure used for storing a dynamic set of strings.

Used for efficient retrieval and storage of keys in a large dataset.

The structure supports operations such as insertion, search, and deletion of keys.

class TrieNode {

	boolean isWord;
	TrieNode[] children;
	
	TrieNode () {
		isWord = false;
		children = new TrieNode[26];
	}
}

Programs

1. 208. Implement Trie (Prefix Tree)
   1. leetcode here

      class Trie {
      
          TrieNode root;
          public Trie() {
              root = new TrieNode();
          }
          
          public void insert(String word) {
              
              int len = word.length();
              int k = 0;
              TrieNode curr = root;
      
              for (int i=0; i<len; i++) {
                  k = word.charAt(i) - 'a';
                  if (curr.children[k] == null) {
                      curr.children[k] = new TrieNode();
                  }
                  curr = curr.children[k];
              }
              curr.isWord = true;
          }
          
          public boolean search(String word) {
              
              int len = word.length();
              int k = 0;
              TrieNode curr = root;
              for (int i=0; i<len; i++) {
                  k = word.charAt(i) - 'a';
                  curr = curr.children[k];
                  if (curr == null) {
                      return false;
                  }
              }
      
              return curr.isWord;
          }
          
          public boolean startsWith(String prefix) {
              
              int len = prefix.length();
              int k = 0;
              TrieNode curr = root;
              for (int i=0; i<len; i++) {
                  k = prefix.charAt(i) - 'a';
                  curr = curr.children[k];
                  if (curr == null) {
                      return false;
                  }
              }
              return true;
          }
      }

2. 14. Longest Common Prefix
   1. leetcode here

      class Solution {
      
          TrieNode root;
      
         private void insert(String str) {
      
              TrieNode curr = root;
              for (char ch: str.toCharArray()) {
                  
                  if (curr.children[ch - 'a'] == null) {
                      curr.children[ch - 'a'] = new TrieNode();
                  }
                  curr = curr.children[ch - 'a'];
              }
              curr.isWord = true;
          }
      
          private int longestCommonPrefixLen(String str) {
              
              TrieNode curr = root;
              int ans = 0;
              for (char ch: str.toCharArray()) {            
                  if (curr.children[ch - 'a'] == null) {
                      break;
                  }
                  curr = curr.children[ch - 'a'];
                  ans ++;
              }
              return ans;
          }
      
          public String longestCommonPrefix(String[] strs) {
              
              root = new TrieNode();
              insert(strs[0]);
              int prefixLen =  strs[0].length();
      
              for (int i=1; i<strs.length; i++) {
                  prefixLen = Math.min(prefixLen, longestCommonPrefixLen(strs[i]));
              }
              return strs[0].substring(0, prefixLen);
          }
      }

3. 139. Word Break
   1. leetcode here

      class Solution {
      
          TrieNode root = new TrieNode('z');
          void insert(String word) {
      
              TrieNode curr = root;
              for (char ch: word.toCharArray()) {
                  
                  if (curr.children[ch - 'a'] == null) {
                      curr.children[ch - 'a'] = new TrieNode(ch);
                  }
                  curr = curr.children[ch - 'a'];
              }
              curr.isEndOfWord = true;
          }
      
          boolean helper(String s, int start, int[] memo) {
      
              if (start == s.length()) {
                  return true;
              }
      
              if (memo[start] != -1) {
                  return memo[start] == 1;
              }
      
              TrieNode curr = root;
              for (int i=start; i<s.length(); i++) {
      
                      int index = s.charAt(i) - 'a';
                      if (curr.children[index] == null) {
                          memo[start]=0;
                          return false;
                      }
                      curr = curr.children[index];
                      if (curr.isEndOfWord && helper(s, i+1, memo)) {
                          memo[start]=1;
                          return true;
                      }
              }
              memo[start]=0;
              return false;
          }
      
          public boolean wordBreak(String s, List<String> wordDict) {
              
              for (String word: wordDict) {
                  insert(word);
              }
              int[] memo = new int[s.length()];
              Arrays.fill(memo, -1);
              return helper(s, 0, memo);
          }
      }
      
      class TrieNode {
      
          char character;
          boolean isEndOfWord;
          TrieNode[] children;
      
          TrieNode(char c) {
              character = c;
              isEndOfWord = false;
              children = new TrieNode[26];
          }
      }