Overview
Figure 1. An example of a trie.
A trie, or a prefix tree, is a type of search tree that is usually used to store strings. Figure 1 is an example when a trie stores [ape,apple,are,art, ...]. Now let’s take a closer look, and it’s not hard to find that:
- Each path from the root to leaves forms a word.
- Each node except for the root node contains a value.
- All the descendants of a node share a common prefix associated to that node. For example,
areandartsharearas the prefix.
There are two operations provided by a trie: inserting a new string, and searching for a given string.
The advantage of using a trie is that, regardless of the number of strings stored in it, the time complexity for both inserting and searching is always O(L) when L is the length of the input string.
Implementations
There are different approaches to implement a trie in Java and Python. Normally we would define a class for the trie node in Java, however, we can alternatively use dictionaries in Python to improve the efficiencies.
Let's take LeetCode 208. Implement Trie (Prefix Tree) as an example.
Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:
You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.Demo:
Java
Define TrieNode
Firstly we need to define a class TrieNode with:
- A boolean variable
isWordto indicate whether we can form a word or it's only a prefix. - An array of
TrieNodenamedchildrento store its children node. - A constructor which initializes
isWordtofalse, and, as only lowercase letters will be used, initializeschildrento an array of size 26.
class TrieNode {
public boolean isWord;
public TrieNode[] children;
public TrieNode(){
children = new TrieNode[26];
isWord = false;
}
}Starting from there, we can initialize a trie structure by simply creating a dummy node by private TrieNode root = new TrieNode();.
insert
Given a new string word, we would iterate through it. Starting from the dummy node root and the first character c, we would check whether c is in root.children:
- if it is, we can move to that node and increment to next character as well;
- if not, we need to initiate a new node so that we can attach
cto the trie.
public void insert(String word) {
// start from the dummy node
TrieNode current_node = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current_node.children[index] == null) {
// if the current character does not exist,
// initialize a new node
current_node.children[index] = new TrieNode();
}
current_node = current_node.children[index];
}
// remember to set isWord to true after
// reaching the end of word
current_node.isWord = true;
}search
Similary to insert, we also start the iteration with the first character and the dummy node. If we do not find the character in its children, we can return false. Remember to check isWord after reaching the end of word.
public boolean search(String word) {
TrieNode current_node = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current_node.children[index] == null) return false;
current_node = current_node.children[index];
}
return current_node.isWord;
}startsWith
The only different to search is that, we do not need to check isWord at the end.
public boolean startsWith(String prefix) {
TrieNode current_node = root;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (current_node.children[index] == null) return false;
current_node = current_node.children[index];
}
return true;
}Full version
class TrieNode {
public boolean isWord;
public TrieNode[] children;
public TrieNode(){
children = new TrieNode[26];
isWord = false;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode current_node = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current_node.children[index] == null) {
current_node.children[index] = new TrieNode();
}
current_node = current_node.children[index];
}
current_node.isWord = true;
}
public boolean search(String word) {
TrieNode current_node = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current_node.children[index] == null) return false;
current_node = current_node.children[index];
}
return current_node.isWord;
}
public boolean startsWith(String prefix) {
TrieNode current_node = root;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (current_node.children[index] == null) return false;
current_node = current_node.children[index];
}
return true;
}
}Python with Dictionaries
For dynamic programming languages like Python, instead of defining a trie node class, we can use a dictionary as a trie node. For each node, we can define a special character such as # to indicate whether it's a word or only a prefix. Otherwise, ideas between Java and Python are quite similar.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word: str) -> None:
current_node = self.root
for char in word:
if not current_node.get(char):
current_node[char] = {}
current_node = current_node[char]
current_node['#'] = True
def search(self, word: str) -> bool:
current_node = self.root
for char in word:
if current_node.get(char):
current_node = current_node[char]
else:
return False
return current_node.get('#')
def startsWith(self, prefix: str) -> bool:
current_node = self.root
for char in prefix:
if current_node.get(char):
current_node = current_node[char]
else:
return False
return True