Question 1 Intro Trie: How to design a dictionary
1. What is the requirement of this dictionary?
search(word)
delete
add
2. Options for data structures
n- # of words
m - the average length of the string/word
HashMap.contain(target)
hashCode: O(m)
string compare: O(m)
Binary Search Tree (Treeset)
ArrayList(sorted, unsorted)
Trie
What is Trie
Retrieve, prefixTrie,
a data structure, more precisely, a search tree
Tries are different from binary search tree
a key is associated with a "path from the root" to a node, instead of associated with a node(说白了就是你的字母是在边上，所以单词在path上)
the edges from a node represent distinct character
The path from the root to each node is a prefix of a word in the dictionary,因此也叫前缀树
Trie class
class TrieNode {
// Map a character to its corresponding child
// 以前的tree child对应的是一个个点，这次是以character作为1，2，3
Map<Character, TrieNode> children;
boolean isWord; //这个点是不是作为结束
int value; // optional. a set doesn't nee this field
}
class TrieNode {
// an array of size 26, each index --> character
TrieNode[] children;
boolean isWord; //这个点是不是作为结束
int value; // optional. a set doesn't nee this field
}TC& SC
Time: worst case guarantee O(m)
Space: worst case O(mn), but usually much better than this. - if the trie is dense, since reusing the common prefix as many as possible, less space is required
Drawbacks
Trie's advanced drawbacks(在硬盘里常有问题)
time - if stored on disk, more random disk accesses(very expensive)
space - every trieNode has extra space consumption--> extra space usage - memory allocation fragmentation, especially when the trie is sparse
Use Case
string or sequence type elements
fast worst-case search/add/delete
grouping common prefixes, both for time/space efficiency
especially when the trie to prefix/matching
Base Operations: 1. search "cat" in the trie
// finding the path from root which is equal to 'cat'
// for reach of the characters in "cat", see if there is an edge associated with it for the next level
public boolean search(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
TrieNode next = cur.children.get(word.charAt(i));
if (next == null) return false;
cur = next;
}
return cur.isWord;
}
// Time: O(word.length)Base Operations: 2. add "carp" into the trie
// finding the path from root which is equal to "carp"
// for each of the character in "carp", see if there is an edge associated with it for the next level
// 1. if there is an edge, go to the corresponding child node
// 2. if there is not, create the child node
public boolean insert(String word) {
if (search(word)) {
return false;
}
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
TrieNode next = cur.children.get(word.charAt(i));
if (next == null) {
next = new TrieNode();
cur.children.put(word.charAt(i), next);
}
cur = next;
// cur.count++;
}
cur.isWord = true;
return true;
}
// TC: O(word.length)Base Operations: 3. delete “apple” from the trie
Solution 1:
Store the path from root to the to-delete node in a stack
Mark the last node as not word
When popping a node form the stack, erase the node if it is not a word and has no children
Solution 2:
所以你再遍历你这个word，然后呢，每次看这接下来有几个单词，如果只剩一个了，剩下的全删了
class TrieNode{
int count; // how many word are on this subtree(inclusive)
Map<Character, TrieNode> children;
boolean isWord; // indicate if the node is the end of the word
}
public boolean delete(String word) {
if (!search(word)) {
return false;
}
root.count--; //你每一次都需要delete
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
TrieNode next = cur.children.get(word.charAt(i));
next.count--;
if (next.count == 0) {
cur.children.remove(word.charAt(i));
return true;
}
cur = next;
}
cur.isWord = false; // e.g. app
return true;
}
// Time O(word.length)Base Operations: 4. find all the words in a given prefix
for example find all with prefix "ca"
step 1: find the node x associated with prefix "ca"
step 2: do DFS on the subtree rooted at x to find all words
Option 1:偷懒就是在这个点上已经存储了，否则你要存path
// option 1
class TrieNode {
// Maps a character to its corresponding child
Map<Character, TrieNode> children;
boolean isWord;
int value; // optional, a set doesn't need this field
string word;
}
public void findAllWordsUnderNode(TrieNode current, List<String> result) {
if (current.isWord) { // this is when we find a word.
result.add(current.word);
// shall we return here? No, children可能还有word
}
// find all branches
for (Entry<Character, TrieNode> child: current.children.EntrySet()) {
findAllWordsUnderNode(child.getValue(), result);
}
}
Option 2:你就是要记录这个stringBuilder
public List<String> findAllWordsWithPrefix(TrieNode root, String prefix) {
TrieNode matchNode = searchNode(root, prefix); // 你要先找到前缀
if (matchNode == null) {
return result;
}
List<String> result = new ArrayList<>();
findAllWordsUnderNode(matchNode, new StringBuilder(prefix), result);
return result;
}
public void findAllWordsUnderNode(TrieNode current, StringBuilder curPath, List<String> result) {
if (current.isWord) { // this is when we find a word
result.add(curPath.toString());// we should not return here, children might have word
}
// all branches
for (Entry<Character, TrieNode> child: current.children.EntrySet()) {
curPath.append(child.getKey());
findAllWordsUnderNode(child.getValue(), curPath, result);
curPath.deleteCharAt(curPath.length() - 1);
}
}TC * SC: O(search) + O(# of result words) = O(height) + O(# of result words)
It can be extended to support more operations, what other possible queries can it support?
Wildcard expression match queries
regular expression match queries
words winthin certain edit distance
e.g. Wildcard
"?" means single character. //.
"*" means >= 0 arbitrary characters. //>=0
Last updated