Trie - rFronteddu/general_wiki GitHub Wiki
A trie, also called prefix tree, is a special form of N-ary tree. Typically used to store, strings, each node represents a string (prefix). Trie are widely used in autocomplete and spell checker.
Common trie representation
Array
Faster but wastes space if some children are not needed
class TrieNode {
public static final n = 26;
public TrieNode[] children = new TrieNode[N];
}
// you can return a children char c: root.children[c-'a']
Map
Slower, more flexible, allocates only what is used.
class TrieNode {
public Map<Character, TrieNode> children = new HashMap<>();
}
// c: root.children.get(c);
Operations
Insertion
init: cur = root
for each char c in target string s:
if cur has no children:
cur[c] = new TrieNode
cur = cur.children[c]
cur is the node which represent s
Search
init: cur = root
for each c in s:
if cur has no children:
search fail
cur = cur.children[c]
search success
Common Applications:
Accelerate DFS Sometimes, we will use Trie to accelerate DFS especially when we do DFS for word games. We provide two word games (Word Squares, Word Search II) for you in this chapter. Try to solve the problem by DFS first and then use Trie to improve the performance.
Store other Data Type We use Trie to store strings in most cases but not always. Maximum XOR of Two Numbers in an Array is an interesting example.
There are also some other use cases, such as IP routing (Longest prefix matching).