题目0208:实现Trie(前缀树)
题目描述
实现一个Trie(前缀树),包含insert,search和startsWith这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
说明:
你可以假设所有的输入都是由小写字母a-z构成的。
保证所有输入均为非空字符串。
解题技巧
-
方法1:实现
-
应用
Trie(发音为"try")或前缀树是一种树数据结构,用于检索字符串数据集中的键。这一高效的数据结构有多种应用:
- 自动补全
- 拼写检查
- IP路由(最长前缀匹配)
- T9(九宫格)打字预测
- 单词游戏
还有其他的数据结构,如平衡树和哈希表,使我们能够在字符串数据集中搜索单词。为什么我们还需要Trie树呢?尽管哈希表可以在O(1)时间内寻找键值,却无法高效的完成以下操作:
找到具有同一前缀的全部键值。
按词典序枚举字符串的数据集。
Trie树优于哈希表的另一个理由是,随着哈希表大小增加,会出现大量的冲突,时间复杂度可能增加到O(n),其中n是插入的键的数量。与哈希表相比,Trie树在存储多个具有相同前缀的键时可以使用较少的空间。此时Trie树只需要O(m)的时间复杂度,其中m为键长。而在平衡树中查找键值需要O(m \log n)时间复杂度。
Trie树的结点结构
Trie树是一个有根的树,其结点具有以下字段:
最多R个指向子结点的链接,其中每个链接对应字母表数据集中的一个字母。
本文中假定R为26,小写拉丁字母的数量。
布尔字段,以指定节点是对应键的结尾还是只是键前缀。
class TrieNode {
// R links to node children
private TrieNode[] links;
private final int R = 26;
private boolean isEnd;
public TrieNode() {
links = new TrieNode[R];
}
public boolean containsKey(char ch) {
return links[ch -'a'] != null;
}
public TrieNode get(char ch) {
return links[ch -'a'];
}
public void put(char ch, TrieNode node) {
links[ch -'a'] = node;
}
public void setEnd() {
isEnd = true;
}
public boolean isEnd() {
return isEnd;
}
}
Trie树中最常见的两个操作是键的插入和查找。
向Trie树中插入键
我们通过搜索Trie树来插入一个键。我们从根开始搜索它对应于第一个键字符的链接。有两种情况:
链接存在。沿着链接移动到树的下一个子层。算法继续搜索下一个键字符。
链接不存在。创建一个新的节点,并将它与父节点的链接相连,该链接与当前的键字符相匹配。
重复以上步骤,直到到达键的最后一个字符,然后将当前节点标记为结束节点,算法完成。
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 (int i = 0; i < word.length(); i++) {
char currentChar = word.charAt(i);
if (!node.containsKey(currentChar)) {
node.put(currentChar, new TrieNode());
}
node = node.get(currentChar);
}
node.setEnd();
}
}
复杂度分析
时间复杂度:O(m),其中m为键长。在算法的每次迭代中,我们要么检查要么创建一个节点,直到到达键尾。只需要m次操作。
空间复杂度:O(m)。最坏的情况下,新插入的键和Trie树中已有的键没有公共前缀。此时需要添加m个结点,使用O(m)空间。
在Trie树中查找键
每个键在trie中表示为从根到内部节点或叶的路径。我们用第一个键字符从根开始,检查当前节点中与键字符对应的链接。有两种情况:
存在链接。我们移动到该链接后面路径中的下一个节点,并继续搜索下一个键字符。
不存在链接。若已无键字符,且当前结点标记为isEnd,则返回true。否则有两种可能,均返回false :
还有键字符剩余,但无法跟随Trie树的键路径,找不到键。
没有键字符剩余,但当前结点没有标记为isEnd。也就是说,待查找键只是Trie树中另一个键的前缀。
class Trie {
...
// search a prefix or whole key in trie and
// returns the node where search ends
private TrieNode searchPrefix(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char curLetter = word.charAt(i);
if (node.containsKey(curLetter)) {
node = node.get(curLetter);
} else {
return null;
}
}
return node;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
}
复杂度分析
时间复杂度 : O(m)O(m)。算法的每一步均搜索下一个键字符。最坏的情况下需要 mm 次操作。
空间复杂度 : O(1)O(1)。
查找Trie树中的键前缀
该方法与在Trie树中搜索键时使用的方法非常相似。我们从根遍历Trie树,直到键前缀中没有字符,或者无法用当前的键字符继续Trie中的路径。与上面提到的"搜索键"算法唯一的区别是,到达键前缀的末尾时,总是返回true。我们不需要考虑当前Trie节点是否用"isend"标记,因为我们搜索的是键的前缀,而不是整个键。
class Trie {
...
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode node = searchPrefix(prefix);
return node != null;
}
}
复杂度分析
时间复杂度:O(m)。
空间复杂度:O(1)。