题解 | #字典树的实现#

思路:题目要求出现的字母均为小写，那么可以创建一个PreTriee的类，其属性成员包括node：单词的下一个字母,isWorld：表示该前缀是否为单词,worldCount：表示该单词插入的数量，prefixCount：表示该前缀插入了多少次。要进行对字段树的插入删除以及查询操作，大体上代码和插入类似：使用循环进行判断即可。值得注意的是，每次插入操作需要把前缀数量+1，因为该题目可可以执行重复插入。

public class Solution {
    class PreTriee{
        PreTriee [] node = new PreTriee[26];
        boolean isWorld = false;
        int worldCount = 0;
        int prefixCount = 0;
        PreTriee(){}
    }
    PreTriee root = new PreTriee(); 
    public String[] trieU (String[][] operators) {
        List<String> res = new ArrayList<>();
        for(int i = 0;i<operators.length;++i){
            switch(operators[i][0]){
                case "1":
                    insert(operators[i][1]);
                    break;
                case "2":
                    delete(operators[i][1]);
                    break;
                case "3":
                    res.add(search(operators[i][1]));
                    break;
                case "4":
                    res.add(""+prefixNumber(operators[i][1]));
                    break;
            }
        }
        String[] r = new String[res.size()];
        for(int i = 0;i<res.size();++i){
            r[i] = res.get(i);
        }
        return r;
    }
    public int prefixNumber(String str){
         PreTriee pretree = root;
        for(int i=0;i<str.length();++i){
            if(pretree.node[str.charAt(i)-'a']==null)return 0;
            else pretree = pretree.node[str.charAt(i)-'a'];
        }
        int count = 0;
        for(int i=0;i<pretree.node.length;++i){
            if(pretree.node[i]!=null)count++;
        }
        return pretree.prefixCount;
    }
    public String search(String str){
        PreTriee pretree = root;
        for(int i=0;i<str.length();++i){
            if(pretree.node[str.charAt(i)-'a']==null)return "NO";
            else pretree = pretree.node[str.charAt(i)-'a'];
        }
        if(pretree.isWorld)return "YES";
        else return "NO";
    }
    public void delete(String str){
        PreTriee pretree = root;
        for(int i = 0;i<str.length();++i){
            if(pretree.node[str.charAt(i)-'a']==null)return;
            else pretree = pretree.node[str.charAt(i)-'a'];
            pretree.prefixCount-=1;
        }
        if(pretree.isWorld&&pretree.worldCount>1){
            pretree.worldCount--;
        }
        else {
            pretree.isWorld = false;
             pretree.worldCount--;
        }
    }
    public void insert(String str){
        PreTriee pretree = root;
        for(int i=0;i<str.length();++i){
            if(pretree.node[str.charAt(i)-'a']==null){
                pretree.node[str.charAt(i)-'a'] = new PreTriee();
            }
            pretree = pretree.node[str.charAt(i)-'a'];
            pretree.prefixCount+=1;
        }
        pretree.isWorld = true;
        pretree.worldCount +=1;
    }
}