题目
方法一:利用数组构建26叉树
插入图示:
全搜索和前缀搜索:
注意:全局匹配匹配完直接返回插入时的标志位
而前缀匹配时,匹配成功后直接返回true 因为不需要往下匹配了
匹配到空trie都统统直接返回false
// 方法一 : 利用数组存储孩子节点
private Trie[] children ; //孩子数组
private boolean isWord ; //标志位
public Trie() {//构造函数
children = new Trie[26];// 初始化为大小为26的数组
isWord = false;//标志位初始化为false
}
//插入操作
public void insert(String word) {
Trie root = this;//给祖先节点赋空对象//此时 孩子数组为空 标志位默认false
for(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标
char ch = word.charAt(i);
int idx = ch - 'a';
if(root.children[idx] == null){ //如果发现当前位置 为null 则是第一次插入,创建新的trie
root.children[idx] = new Trie();
}
root = root.children[idx]; //如果当前位置存在,那么将指针指向下一层
}
root.isWord = true; //插入完成 标记为true
}
//全匹配操作
public boolean search(String word) {
Trie root = this;//获得当前对象
for(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标
char ch = word.charAt(i);
int idx = ch - 'a';
if(root.children[idx] == null){ //如果发现当前位置 为null 说明搜索不到 直接return fasle
return false;
}
root = root.children[idx]; //如果当前位置存在,那么将指针指向下一层继续搜索
}
return root.isWord;//如果能搜索到 则直接就是返回本来的状态值
}
// 前缀匹配
public boolean startsWith(String prefix) {
Trie root = this;//获得当前对象
for(int i = 0 ; i<prefix.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标`在这里插入代码片`
char ch = prefix.charAt(i);
int idx = ch - 'a';
if(root.children[idx] == null){ //如果发现当前位置 为null 说明搜索不到 直接return fasle
return false;
}
root = root.children[idx]; //如果当前位置存在,那么将指针指向下一层继续搜索
}
return true;//如果能搜索到 则直接就是返回true
}
方法二:利用哈希表构建26叉树
相比较上面的用数组构建26叉树,其实也可以采用哈希表存储子节点
文章来源:https://www.toymoban.com/news/detail-706226.html
方法二 : 利用hashmap存储孩子节点
private Map<Character,Trie> children ; //孩子哈希表 key 为父节点 value为子trie节点
private boolean isWord ; //标志位
public Trie() {//构造函数
children = new HashMap<>();// 初始化哈希表
isWord = false;//标志位初始化为false
}
//插入操作
public void insert(String word) {
Trie root = this;//给祖先节点赋空对象
for(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标
char ch = word.charAt(i);
Trie node = root.children.get(ch);
if(node == null){ //如果发现当前位置 为null 则是第一次插入,创建新的trie
root.children.put(ch,new Trie());
}
root = root.children.get(ch); //如果当前位置存在,那么将指针指向下一层
}
root.isWord = true; //插入完成 标记为true
}
//全匹配操作
public boolean search(String word) {
Trie root = this;//获得当前对象
for(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标
char ch = word.charAt(i);
Trie node = root.children.get(ch);
if(node == null){ //如果发现当前位置 为null 说明搜索不到 直接return fasle
return false;
}
root = root.children.get(ch); //如果当前位置存在,那么将指针指向下一层继续搜索
}
return root.isWord;//如果能搜索到 则直接就是返回本来的状态值
}
// 前缀匹配
public boolean startsWith(String prefix) {
Trie root = this;//获得当前对象
for(int i = 0 ; i<prefix.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标
char ch = prefix.charAt(i);
Trie node = root.children.get(ch);
if(node == null){ //如果发现当前位置 为null 说明搜索不到 直接return fasle
return false;
}
root = root.children.get(ch); //如果当前位置存在,那么将指针指向下一层继续搜索
}
return true;//如果能搜索到 则直接就是返回true
}
参考:Leetcode 208 实现Trie(前缀树)文章来源地址https://www.toymoban.com/news/detail-706226.html
到了这里,关于【LeetCode-中等题】208. 实现 Trie (前缀树)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!