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
LeetCode 212 - Word Search II: find all words in the board
Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.- Trie: O(rows * cols * m * 4^m) - m is the average len of word
- Reuse input board[][] as visited
- Simple DFS: O(n * rows * cols * 4^2n)
public List findWords(char[][] board, String[] words) { List res = new ArrayList<>(); TrieNode root = buildTrie(words); for(int i = 0; i < board.length; i++) { for(int j = 0; j < board[0].length; j++) { dfs(board, i, j, root, res); } } return res; } public void dfs(char[][] board, int i, int j, TrieNode p, List res) { char c = board[i][j]; if(c == '#' || p.next[c - 'a'] == null) return; p = p.next[c - 'a']; if(p.word != null) { // found one res.add(p.word); p.word = null; // de-duplicate } board[i][j] = '#'; if(i > 0) dfs(board, i - 1, j ,p, res); if(j > 0) dfs(board, i, j - 1, p, res); if(i < board.length - 1) dfs(board, i + 1, j, p, res); if(j < board[0].length - 1) dfs(board, i, j + 1, p, res); board[i][j] = c; } public TrieNode buildTrie(String[] words) { TrieNode root = new TrieNode(); for(String w : words) { TrieNode p = root; for(char c : w.toCharArray()) { int i = c - 'a'; if(p.next[i] == null) p.next[i] = new TrieNode(); p = p.next[i]; } p.word = w; } return root; } class TrieNode { TrieNode[] next = new TrieNode[26]; String word; }- Trie: O(rows * cols * m * 4^m) - m is the average len of word
[LeetCode 379 - Design Phone Directory]
LeetCode 642 - Design Search Autocomplete System
- TrieNode: Map<String, Integer> freq;
- store value in end node and all TrieNode
- Store string(part) in TrieNode, handle it reversely
LeetCode 425 - Word Squares: find all word squares you can build from them
- A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).
- Trie + brute force: start with every world and try
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
- LeetCode 720 - Longest Word in Dictionary: w -> wo … -> world
- pre-sort words alphabetically + dp: nlogn
- Trie + DFS, prune
- if (word.length() < best.length() || (word.length() == best.length() && word > best)) continue;
- Trie + BFS
public String findLongestWord() { String result = null; Queue<TrieNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TrieNode node = queue.poll(); for (int j = 25; j >= 0; j--) { if (node.children[j] != null && node.children[j].isWord) { result = node.children[j].word; queue.offer(node.children[j]); } } } } return result; }Trie + DP + DFS
- HARD: LintCode 623 - K EDIT DISTANCE: find all the strings for each the edit distance with the target no greater than k
Bit Trie
- search each bit: trie.maxXOR(num)
Trie[] children = new Trie[2];- LeetCode 421 - Maximum XOR of Two Numbers in an Array
- bit trie
- 32n + bit prefix
- O(32n) -> bit by bit
- divide and conquer - nlogn
- Minimum XOR Value Pair -bit + trie:O(n) or pre-sort: O(nlogn)
Prefix Xors + Bit Trie
- Find the maximum subarray XOR in a given array
- prefix xor, xor[i,j]=prefix-xor[i]^prefix-xor[j] + trie
- Subarray with XOR less than k
- Codefoces 282E - Sausage Maximization
Suffix Trie
- Multiple Patterns Search - Suffix Tree
- Longest Repeated Substring
- DISUBSTR - Count of distinct substrings of a string
- Given a string band an array of smaller strings T, design a method to search b for each small string in T.
Generalized Suffix Tree
- Longest Common Substring
- [LeetCode 5 - Longest Palindromic Substring]
- DP: time O(N^2), space O(N^2)
- Expand at center: time O(N^2), space O(1)
- [Manacher’s Algorithm]
- Suffix trie - TODO
Examples
- Uber Prepare: Web Address
- LeetCode 527 - Word Abbreviation: generate minimal possible abbreviations for every word in the list
- HARD: LeetCode 30 - Substring with Concatenation of All Words
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;
}
} 