思路:
这是一种叫做 单词查找树 的结构。它由字符串键中所有的字符构造而成，允许使用被查找键中的字符进行查找。其中包括插入、查找、删除，寻找前缀等操作. [站外图片上传中...(image-832521-1636112029289)]
代码:
代码语言：javascript复制class Trie {
//定义前缀树结点结构
public class TrieNode {
//表示当前节点所能链接到其他节点的个数（在删除操作中会用到）
public int path;
//表示以当前节点为结尾的单词的个数
public int end;
//表示当前节点能链接到的所有节点。
public HashMap<Character, TrieNode> next;
public TrieNode() {
path = 0;
end = 0;
next = new HashMap<>();
}
}
//跟结点
private TrieNode root;
public Trie() {
root=new TrieNode();
}
public void insert(String word) {
if(word == null || word.length()==0) {
return ;
}
TrieNode node=root;
for (int i = 0; i < word.length(); i ) {
char ch=word.charAt(i);
if (!node.next.containsKey(ch)){
node.next.put(ch,new TrieNode());
}
node = node.next.get(ch);
node.path ;
}
node.end ;
}
public boolean search(String word) {
if(word==null||word.length()==0) {
return false;
}
TrieNode node=root;
for (int i = 0; i < word.length(); i ) {
char currChar=word.charAt(i);
if (!node.next.containsKey(currChar)){
return false;
}else{
node=node.next.get(currChar);
}
}
//如果这个没有以此为截至结点的就返回false
if (node.end==0){
return false;
}
return true;
}
public boolean startsWith(String prefix) {
if(prefix==null||prefix.length()==0) {
return false;
}
TrieNode node=root;
for (int i = 0; i < prefix.length(); i ) {
char currChar=prefix.charAt(i);
if (!node.next.containsKey(currChar)){
return false;
}else{
node=node.next.get(currChar);
}
}
return true;
}
}补充
如果我们有delete操作 delete操作同上述操作大致相同，这里需要使用到path变量，回忆一下，path：表示当前节点所能链接到其他节点的个数。还以五个单词为例，例如删除'the'，当匹配到‘t’时，由于进行path--操作后，此时判断path为0，过可直接将当前节点置空，后面的数据则不用再去遍历即可。java中的垃圾回收机制会处理其他的被断开的节点，如果在C 中，则需要全部匹配，之后调用析构函数去操作
代码语言：javascript复制public void delete(String word){
if(word == null || word.equals("") || !search(word)) return ;
TrieNode node = root;
for (int i = 0; i < word.length(); i ) {
char ch = word.charAt(i);
if(--node.next.get(ch).path == 0){
node.next.remove(ch);
return;
}
node = node.next.get(ch);
}
node.end--;
}参考作者：Geralt_U 链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/208-shi-xian-trie-qian-zhui-shu-bao-gua-insert-sea/
