7月23日：实现前缀树
题目如下：
很明显这是一道关于设计数据结构的题目。但是本菜鸡拿到这道题目的第一想法就是用hashSet来存字符串，这样的话插入和查找字符串是否存在就比较方便了，但查前缀就变得有些麻烦，虽然麻烦但是还是可以完成前缀查询的。下面是菜鸡思路代码：
class Trie {
Set<String> hash;
/** Initialize your data structure here. */
public Trie() {
hash = new HashSet<>();
}
/** Inserts a word into the trie. */
public void insert(String word) {
hash.add(word);
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
if(hash.contains(word))
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) {
boolean p = false;
for(String str:hash){
int flage=0;
if(str.length()<prefix.length()) continue;
for(int i=0;i<prefix.length();i++){
if(prefix.charAt(i)==str.charAt(i))
continue;
else
{
flage=1;
break;
}
}
if(flage==0)
return true;
}
return p;
}
}
看到这个结果，确实是菜的扣脚。。。。。
然后还是学习leetcode官方大佬的解法吧。
首先官方使用前缀树来表示字符串，前缀树看上面那幅图貌似不太形象。实际上前缀树是这个样子的，如下图：
像我们常接触的树形结构大多是二叉树，或者是b树或者b+树，前缀树也是一棵多叉树。
下面是前缀树的数据结构：
下面是官方完整代码：
class Trie {
class TrieNode {
// R links to node children
private TrieNode[] links;
private final int R = 26;
private boolean isEnd;
public TrieNode() {
links = new TrieNode[R];
}
public boolean containsKey(char ch) {
return links[ch -'a'] != null;
}
public TrieNode get(char ch) {
return links[ch -'a'];
}
public void put(char ch, TrieNode node) {
links[ch -'a'] = node;
}
public void setEnd() {
isEnd = true;
}
public boolean isEnd() {
return isEnd;
}
}
private 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++) {
char currentChar = word.charAt(i);
if (!node.containsKey(currentChar)) {
node.put(currentChar, new TrieNode());
}
node = node.get(currentChar);
}
node.setEnd();
}
private TrieNode searchPrefix(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char curLetter = word.charAt(i);
if (node.containsKey(curLetter)) {
node = node.get(curLetter);
} else {
return null;
}
}
return node;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
public boolean startsWith(String prefix) {
TrieNode node = searchPrefix(prefix);
return node != null;
}
}
官方题解还是蛮快的哇。