数据结构之字典树Trie
字典树Trie
字典树也叫前缀树,是一种在字符串查找,前缀匹配等问题广泛应用的算法,为什么使用字典树呢?我们都知道如果对于一个存储有n个条目的数据集做查询,线性结构的时间复杂度是O(n),这是相当恐怖的,改进的基于红黑树的查询时间复杂度是O(logn),虽然已经好很多,但是当n非常大时,这个时间复杂度还是不能接受的。而字典树能做到查询的时间复杂度和数据集存储的数目n无关,而仅和被查询的字符串长度有关,所以它在查找时只有O(1)的时间复杂度。这是怎么做到的呢,其实很简单,下图是某存储英文的字典树的结构:
Trie该树中存储了英语单词,如果要查询某个单词,比如,只需要先找到w,再找到i、n、d即可。可见对每个单词的查找只需要查找单词长度次,而且每次查找只需查找26次之内(即便算上大写也在52次之内)。
Trie数据结构设计要点:
- 添加操作:从根开始向下,如果某个节点没有则拓展一个新节点,添加完毕后在最后一个节点处将标志置true;
- 查询操作:基本过程与插入相同,向下查找,如果中间遇到一次节点不存在,直接返回false,一直向下查找,最终返回标志位;
- 每遍历到一个叶子节点,就查到一个单词(条目);
- 可能某个单词是其它单词的前缀,如果没到叶子节点就存储了一个单词,则将此处标志置true。
字典树的实现
首先考虑节点结构,并假设这里的节点仅存储小写英文单词,故每个节点下应该有26个分支(实际如何存储根据具体情境):
class Node{
char c;
Node next[26];//指向下一个节点
}
不过由于在寻找下一个节点时,我们实际上已经知道了要找哪个,故可以将当前节点和和其指向的节点存储为一个整体(相当于存储是在边上),考虑到Java中TreeMap中键值对中一个键对应的值可以添加多个,这些值组成一个keySet,故节点设计为:
class Node{
boolean isWord;
Map<char,Node> next;
}
其中isWord用于标识单词结尾,从而Trie类:
import java.util.TreeMap;
public class Trie {//不需要泛型,这里仅解决字符串类问题
private class Node{//Trie的节点类
public boolean isWord;
public TreeMap<Character,Node> next;
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<>();
}
public Node(){
this(false);//表示使用上面的构造函数
}
}
private Node root;
private int size;
public Trie(){
root = new Node();
size = 0;
}
//获取Trie中的单词数量
public int getSize(){
return size;
}
//向Trie中添加新单词(字符串)
public void add(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null)//如果映射中没有包含到c的映射
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
if (!cur.isWord) {//首先检查该单词是否已经存在
cur.isWord = true;
//此时来到了当前添加单词的最后节点,但不一定是叶子节点,因为可能是别的单词前缀
size++;
}
}//作业:使用递归写法完成添加操作
public boolean contains(String word){
//查询单词word是否在Trie中
Node cur = root;
for(int i=0;i<word.length();i++){
char c = word.charAt(i);
if(cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return cur.isWord;
}//作业,递归写法
//其实Trie也是一个集合
public boolean isPrefix(String prefix){
//查询Trie中是否有单词以prefix为前缀(一个单词也是本身的前缀)
Node cur = root;
for(int i=0;i<prefix.length();i++){
char c = prefix.charAt(i);
if(cur.next.get(c) == null)
return false;
cur = cur.next.get(c);
}
return true;//和查询单词操作类似,不过无需检查是否包含单词
//作业:BSTSet中查询前缀
}
}
可以看到,Trie类的实现我们借助了TreeMap等底层数据结构,这正是数据结构的魅力,就像乐高积木一样,由一些基础的木块一步步搭建出美丽的艺术品。
Trie的应用——LeetCode207、211
LeetCode207不再介绍,就是设计一个字典树类,支持添加和查找操作,我们实现的类修改下类名即可。
LeetCode211
这个题目其实和Trie类要完成的工作类似,不过加入了一些更灵活的条件(简易正则表达式),只需对我们的Trie类做小部分修改即可:
import java.util.TreeMap;
class WordDictionary {
private class Node{//Trie的节点类
public boolean isWord;
public TreeMap<Character,Node> next;
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<>();
}
public Node(){
this(false);//表示使用上面的构造函数
}
}
private Node root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new Node();
}
public void addWord(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null)//如果映射中没有包含到c的映射
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
if (!cur.isWord) //首先检查该单词是否已经存在
cur.isWord = true;
}
public boolean search(String word) {
return match(root, word,0);
}
private boolean match(Node node, String word, int index) {
//从index处开始匹配
if (index == word.length())
return node.isWord;//递归终止条件,word匹配完毕,若为true则返回匹配成功,false匹配失败
char c = word.charAt(index);
if (c == '.') {
for (char nextChar : node.next.keySet()) {//是.则遍历所有字母
if (match(node.next.get(nextChar), word, index + 1))
return true;
}
return false;
} else {
if (node.next.get(c) == null)
return false;
return match(node.next.get(c), word, index + 1);//继续匹配后面的部分
}
}
}
可以发现,我们只对查询函数做了比较大的改动,而查询主要是基于递归实现的。
提交,获得通过!