admin管理员组文章数量:1636940
题目链接:https://leetcode/problems/implement-trie-prefix-tree/
题目:
Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
解题思路:
这道题的考点是设计前缀树。
一开始并不知道什么是前缀树,所以无法下手解决。
Trie树,又称为字典树、单词查找树或者前缀树,是一种用于快速检索的多叉数结构。例如,英文字母的字典树是26叉数,数字的字典树是10叉树。
Trie树的基本性质有三点,归纳为:
1. 根节点不包含字符,根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符串不相同。
使用 HashMap
class TrieNode {
// Initialize your data structure here.
char c;
HashMap<Character, TrieNode> children = new HashMap();
boolean isLeaf;
public TrieNode() {}
public TrieNode(char c) {
this.c = c;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
HashMap<Character, TrieNode> children = root.children;
for(int i = 0; i < word.length(); i ++) {
char c = word.charAt(i);
TrieNode t;
if(children.containsKey(c)) {
t = children.get(c);
} else {
t = new TrieNode(c);
children.put(c, t);
}
children = t.children;
if(i == word.length() - 1)
t.isLeaf = true;
}
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode t = searchNode(word);
if(t != null && t.isLeaf == true )
return true;
else
return false;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if(searchNode(prefix) == null)
return false;
else
return true;
}
public TrieNode searchNode(String word) {
HashMap<Character, TrieNode> children = root.children;
TrieNode t = null;
for(int i = 0; i < word.length(); i ++) {
char c = word.charAt(i);
if(children.containsKey(c)) {
t = children.get(c);
} else {
return null;
}
children = t.children;
}
return t;
}
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
14 / 14 test cases passed.
Status: Accepted
Runtime: 52 ms
版权声明:本文标题:208Implement Trie (Prefix Tree) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1729233812a1191761.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论