第15个算法-实现 Trie (前缀树)（LeetCode）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了第15个算法-实现 Trie (前缀树)（LeetCode），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2688字，纯文字阅读大概需要4分钟。
内容图文
解法代码来源 ：https://blog.csdn.net/whdAlive/article/details/81084793
算法来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree
实现一个 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构成的。 - 保证所有输入均为非空字符串。
网上找了一些解法
class Trie {
//根节点
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
//初始化根节点
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = this.root;
//遍历
for(char c: word.toCharArray()){
if(node.children[c-‘a‘]==null){
node.children[c-‘a‘]=new TrieNode();
}
node = node.children[c-‘a‘];
}
node.item = word;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = this.root;
//遍历
for(char c:word.toCharArray()){
if(node.children[c-‘a‘]==null){
return false;
}
node = node.children[c-‘a‘];
}
return node.item.equals(word);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = this.root;
//遍历
for(char c: prefix.toCharArray()){
if(node.children[c-‘a‘]==null){
return false;
}
node = node.children[c-‘a‘];
}
return true;
}
//定义 前缀树节点 的结构
class TrieNode{
//孩子节点，分别记录26个字母
TrieNode[] children = new TrieNode[26];
//当前的节点（叶子节点）对应的单词
String item = "";
}
}
提交后优秀解法
class Trie {
private static class TrieNode {
boolean isExist;
TrieNode[] nodes;
TrieNode() {
isExist = false;
nodes = new TrieNode[26];
}
TrieNode put(char c) {
if (nodes[c-‘a‘] == null) {
nodes[c-‘a‘] = new TrieNode();
}
return nodes[c-‘a‘];
}
TrieNode get(char c) {
return nodes[c-‘a‘];
}
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
curr = curr.put(c);
}
curr.isExist = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
curr = curr.get(c);
if (curr == null) {
return false;
}
}
return curr.isExist;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode curr = root;
for (char c : prefix.toCharArray()) {
curr = curr.get(c);
if (curr == null) {
return false;
}
}
return true;
}
}
每天看一些算法，没有时间去研究，只能学习。
原文：https://www.cnblogs.com/liutian1912/p/11254402.html
内容总结
以上是互联网集市为您收集整理的第15个算法-实现 Trie (前缀树)（LeetCode）全部内容，希望文章能够帮你解决第15个算法-实现 Trie (前缀树)（LeetCode）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。