字典树Trie
-
音同try，又称前缀树，是一颗有根树，根节点到树节点的一个路径就代表一个单词，多用于关键词检索，自动补完和拼写检查
-
用空间换时间：借公共前缀来降低查询时间的开销
-
根节点无内容
208.实现Trie
复习一下this指针：
-
cpp给每个非静态的成员函数都增加了一个隐藏（不能显式地写出来）的指针参数this，指向当前对象
-
在函数体中所有成员变量的操作都是通过该指针访问
-
是个形参，存储在栈区（寄存器register）
成员变量（Private）：
- 节点两个字段：
- 指向子节点的指针数组children
- 布尔字段isEnd
功能函数（public）：
-
插入insert：
-
存在children--沿指针移动
-
不存在--创建，记录在children数组对应位置上
-
-
查询search：
-
存在children--后移
-
存在prefix--后移
-
存在字符串--前缀末尾对应节点的isEnd为true
-
不存在--prefix不匹配
-
-
查找前缀prefix：
-
存在children--后移
-
不存在--说明字典树中不包含该前缀，返回空指针nullptr
-
-
析构函数deconstruction：
- trie对象没有析构函数，用的默认析构函数。new出来的对象不delete释放内存，多了会泄露
AC：vector数组构建Trie
#include<iostream>
#include<string>
#include<vector>
using namespace std;
//vector动态数组方法
class Trie {
private:
//两个字段
vector<Trie*> children;
bool isEnd;
Trie* searchPrefix(string prefix){
Trie* node=this;
//this pointer, Trie* type
for(char ch:prefix){
//借ASCII码求字符下标，将字母转为数字
ch-='a';
//某字符不存在于前缀中
if(node->children[ch]==nullptr)
return nullptr;
//存在则后移
node=node->children[ch];
}
return node;
}
public:
//construction
Trie():children(26),isEnd(false) {}
void insert(string word) {
Trie* node=this;
for(char ch:word){
ch-='a';
if(node->children[ch]==nullptr)
node->children[ch]=new Trie();
//存在或生成子节点后后移
node=node->children[ch];
}
node->isEnd=true;//prefix前缀的末尾
}
bool search(string word) {
Trie* node=this->searchPrefix(word);
return node!=nullptr && node->isEnd;
}
bool startsWith(string prefix) {
return this->searchPrefix(prefix)!=nullptr;
}
};
int main(){
Trie* object;
object=new Trie();
object->insert("hello");
bool flag;
flag=object->search("hello");
if(flag)
cout<<"word exists";
else cout<<"word does not exist";
return 0;
}
vocal，真??
Java版本（实现了数组和哈希两种方式的Trie）
数组
public class Trie{
class TrieNode{
TrieNode son[];
boolean idEnd;
public TrieNode()
{
son=new TrieNode[26];
}
}
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++)//枚举字符串
{
int index=word.charAt(i)-'a';//找到26个对应位置
if(node.son[index]==null)//如果为空需要创建
{
node.son[index]=new TrieNode();
}
node=node.son[index];
}
node.isEnd=true;//最后一个节点
}
public boolean search(String word) {
TrieNode node=root;
for(int i=0;i<word.length();i++)
{
int index=word.charAt(i)-'a';
if(node.son[index]==null)//为null直接返回false
{
return false;
}
node=node.son[index];
}
return node.isEnd==true;
}
public boolean startsWith(String prefix) {
TrieNode node=root;
for(int i=0;i<prefix.length();i++)
{
int index=prefix.charAt(i)-'a';
if(node.son[index]==null)
{
return false;
}
node=node.son[index];
}
//能执行到最后即返回true
return true;
}
}
哈希表
import java.util.HashMap;
import java.util.Map;
public class Trie{
class TrieNode{
Map<Character,TrieNode> sonMap;
boolean idEnd;
public TrieNode()
{
sonMap=new HashMap<>();
}
}
TrieNode root;
public Trie()
{
root=new TrieNode();
}
public void insert(String word) {
TrieNode node=root;
for(int i=0;i<word.length();i++)
{
char ch=word.charAt(i);
if(!node.sonMap.containsKey(ch))
//不存在插入
{
node.sonMap.put(ch,new TrieNode());
}
node=node.sonMap.get(ch);
}
node.idEnd=true;
}
public boolean search(String word) {
TrieNode node=root;
for(int i=0;i<word.length();i++)
{
char ch=word.charAt(i);
if(!node.sonMap.containsKey(ch))
{
return false;
}
node=node.sonMap.get(ch);
}
return node.idEnd==true;
//必须标记为true证明有该字符串
}
public boolean startsWith(String prefix) {
TrieNode node=root;
for(int i=0;i<prefix.length();i++)
{
char ch=prefix.charAt(i);
if(!node.sonMap.containsKey(ch))
{
return false;
}
node=node.sonMap.get(ch);
}
return true;
//执行到最后一步即可
}
}