赞
踩
Trie(发音类似 “try”)或者说前缀树是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。
其核心是使用「边」来代表有无字符,使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。
Trie结构:
其中红色节点表示一个单词的结尾。
public void insert(String word)
:
我们从字典树的根开始查找前缀,对于当前字符对应的子节点,有两种情况:
重复以上步骤,直到处理字符串的最后一个字符,然后将当前节点标记为字符串的结尾。
public Trie searchPrefix(String prefix)
:
我们从字典树的根开始查找前缀,对于当前字符对应的子节点,有两种情况:
重复以上步骤,直到返回空指针或搜索完前缀的最后一个字符。
isEnd==true
,则说明字典树中存在该字符串。1、Trie树(又叫「前缀树」或「字典树」)是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构,这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
2、在纯算法领域,前缀树算是一种比较常用的数据结构,但如果是在工程中,不考虑前缀匹配的话,基本上使用hash就可以满足要求了。
—>例如:Leetcode「208. 实现 Trie (前缀树)」
请你实现 Trie 类:
Trie()
初始化前缀树对象。void insert(String word)
向前缀树中插入字符串 word 。boolean search(String word)
如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。boolean startsWith(String prefix)
如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。示例:
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
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
class Trie { private Trie[] children;//指向子节点的指针数组children private boolean isEnd;//表明该节点是否为字符串的结尾 public Trie() { children=new Trie[26];//于本题数组长度为26,即小写英文字母的数量 isEnd=false;//初始化为false } public void insert(String word) { Trie node = this; for(int i=0;i<word.length();i++){ char ch=word.charAt(i); int index=ch-'a'; //子节点不存在,创建一个新的子节点,记录在children数组的对应位置上 if(node.children[index]==null){ node.children[index]=new Trie(); } //沿着指针移动到子节点,继续搜索下一个字符 node=node.children[index]; } node.isEnd=true; } public boolean search(String word) { Trie node = searchPrefix(word); return node!=null&&node.isEnd; } public boolean startsWith(String prefix) { return searchPrefix(prefix)!=null; } public Trie searchPrefix(String prefix){ Trie node = this; for(int i=0;i<prefix.length();i++){ char ch=prefix.charAt(i); int index=ch-'a'; //子节点不存在,说明字典树中不包含该前缀,返回空指针 if(node.children[index]==null){ return null; } //沿着指针移动到子节点 node=node.children[index]; } return node; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */
复杂度分析:
时间:初始化为O(1),其余操作为O(|S|),其中|S|为每次插入/查询的字符串长度。
空间:O(∣T∣⋅Σ),其中 ∣T∣ 为所有插入字符串的长度之和,Σ为字符集的大小,本题 Σ=26。
实际需求中不可能只有26个字母,也许有大小写,也许有其他的符号,因此我们需要使用其他的数据结构。
第二版:
class Node{
public boolean isWord;
public Map<Character,Node> next;
}
public class Trie { private class Node{ public boolean isWord; public TreeMap<Character,Node> next; public Node(boolean isWord){ this.isWord = isWord; this.next = new TreeMap<>(); } public Node(){ this(false); } } private Node root; private int size; public Trie(){ this.root = new Node(); this.size = 0; } /** * 返回Trie节点数 */ public int getSize(){ return this.size; } }
向字典树中添加节点的步骤如图:
//添加单词 public void add(String word){ Node curr = root; for(int i=0;i<word.length();i++){ char c = word.charAt(i); if(curr.next.get(c)==null){ curr.next.put(c,new Node());//没有该节点,直接添加新的 } curr = curr.next.get(c);//有该节点,移动curr,继续查找下一节点 } if(!curr.isWord){//如果之前已经存在该单词了size不能加1 curr.isWord = true; size++;//Trie的节点数 } }
//查询单词
public boolean contains(String word){
Node curr = root;
for(int i=0;i<word.length();i++){
char c = word.charAt(i);
if(curr.next.get(c)==null){
return false;//无下一个值的节点,直接返回false
}
curr = curr.next.get(c);
}
return curr.isWord;//单词到达末尾,根据isWord标志判断
}
//查询在Trie中是否有单词以prefix为前缀
public boolean isPrefix(String prefix){
Node curr = root;
for(int i=0;i<prefix.length();i++){
char c = prefix.charAt(i);
if(curr.next.get(c)==null){
return false;
}
curr = curr.next.get(c);
}
return true;
}
删除节点有以下四种情况:
//删除单词 public void delete(String word){ Stack<Node> preNodes = new Stack<>(); //删除前查找是否存在这个单词,存在才能删除 if(!contains(word)){ return;//不存在该单词,直接返回 } Node curr = root; for(int i=0;i<word.length();i++){ char c = word.charAt(i); preNodes.push(curr);//添加前驱节点 curr = curr.next.get(c); } if(curr.next.size()==0){//到了单词末尾,节点是叶子节点 for(int i=word.length()-1;i>=0;i--){ char c = word.charAt(i); Node pre = preNodes.pop();//获得前驱节点 //判断是否为其他单词的结尾,是则停止删除节点【情况3】 //判断待删除节点是否还有其他孩子,有则停止删除节点【情况4】 if((i!=word.length()-1&&pre.next.get(c).isWord)||pre.next.get(c).next.size()!=0){ break; } pre.next.remove(c);//删除节点【情况1】 } }else{ curr.isWord = false;//情况2 } size--; }
上面实现的Trie中,我们是使用TreeMap
来保存节点的所有子节点,也可以用HashMap
来保存,效率会更高:
public Node(boolean isWord){
this.isWord = isWord;
this.next = new HashMap<>();
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。