题解 | #字典树的实现#

import java.util.*;


public class Solution {
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    // 定义一个字典树的结构，一个是节点内容，另外一个是节点对应的一些特征信息比如多少个单词经过这个节点以及多少个单词以这个节点结尾，这些特征主要是为了方便后续遍历时候的统计
    public static class TireTree{
	  	// 定义一个节点的结构
        public static class TreeNode{
            public int pathNumber;//表示多少个单词公用这个节点
            public int endNumber;//表示多少个单词以这个节点结尾
            public Map<Character,TreeNode> map;
            public TreeNode(){
                pathNumber=0;
                endNumber=0;
                map=new HashMap<>();
            }
        }
        private TreeNode root;

        public TireTree(){
            root = new TreeNode();
        }
        // 将一个单词插入到字典树
        public void insert(String word){
            if(word==null||word.length()==0){
                return;
            }
            TreeNode node = root;
            for(int i=0;i<word.length();i++){
                char ch=word.charAt(i);
                //若没有对应的节点，需要创建节点，若有了节点，需要迭代到下一个节点，并且让节点对应的pathNumber++
                if(!node.map.containsKey(ch)){
                    node.map.put(ch,new TreeNode());
                }
                node = node.map.get(ch);
                node.pathNumber++;
            }
            //结束之后需要将以这个节点为终点的数量+1
            node.endNumber++;
        }
        // 查询一个单词是否在字典数当中
        public boolean search(String word){
            if(word==null||word.length()==0){
                return false;
            }
            TreeNode node=root;
            for(int i=0;i<word.length();i++){
                char ch=word.charAt(i);
                if(!node.map.containsKey(ch)){
                    return false;
                }
                node=node.map.get(ch);
            }
            return node.endNumber!=0;
        }
        // 删除一个单词路径
        public void delete(String word){
            // 需要先判断这个单词是不是在字典树当中
            if(search(word)){
                //给每层的node的pathNumber--，最后记得给最后一个节点的endNumber--
                TreeNode node=root;
                for(int i=0;i<word.length();i++){
                    char ch=word.charAt(i);
				  	// 这里其实是一个优化，或者说对于后续的节点来说，如果没有了经过的节点需要一个一个的全部删除掉
                    if((node.map.get(ch).pathNumber--)==0){
                        node.map.remove(ch);
                        return;
                    }
                    node=node.map.get(ch);
                }
                node.endNumber--;
            }
        }
        public int preSearch(String preWord){
            TreeNode node=root;
            for(int i=0;i<preWord.length();i++){
                char ch=preWord.charAt(i);
                if(!node.map.containsKey(ch)){
                    return 0;
                }
                node=node.map.get(ch);
            }
            return node.pathNumber;
        }

    }
    public String[] trieU (String[][] operators) {
        // write code here
        List<String> res=new ArrayList<>();
        if(operators==null||operators.length==0){
            return new String[0];
        }
        int len=operators.length;
        TireTree tree = new TireTree();
        for(int i=0;i<len;i++){
            String op=operators[i][0];
            String word=operators[i][1];
            if("1".equals(op)){
                tree.insert(word);
            }else if("2".equals(op)){
                tree.delete(word);
            }else if("3".equals(op)){
                if(tree.search(word)){
                    res.add("YES");
                }else{
                    res.add("NO");
                }
            }else if("4".equals(op)){
                res.add(""+tree.preSearch(word));
            }
        }
        return res.toArray(new String[res.size()]);
    }
}