题解 | #字典树的实现，O(n)#

import java.util.*;

//前缀树节点
class TrieNode {
    TrieNode[] chs ;//保存子节点
    int count ;//以该节点结尾的前缀 的单词数量
    boolean isEnd ;//该节点是否为一个单词的结尾
    String word ;//该节点若为一个单词的结尾，保存这个单词
    TrieNode() {
        this.chs = new TrieNode[26] ;//由于本题只涉及到26个小写字母，使用数组作为hash表（一般用Map）
        this.count = 0 ;
        this.isEnd = false ;
        this.word = null ;
    }
}

public class Solution {
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    private TrieNode root = new TrieNode() ;//根节点不代表任何字母，根节点的儿子节点代表 单词首字母
    public String[] trieU (String[][] operators) {
        List<String> list = new ArrayList<>() ;
        for(String[] arr : operators) {
            String opt = arr[0] ;
            String word = arr[1] ;
            switch(opt) {
                case "1": insert(word) ; break ;
                case "2": delete(word) ; break ;
                case "3": list.add(search(word) == true ? "YES" : "NO") ;break ;
                case "4": list.add(String.valueOf(prefixNumber(word))) ;break ;
            }
        }
        String res[] = new String[list.size()] ;
        return list.toArray(res) ;
    }
    public void insert(String word) {
        char[] arr = word.toCharArray() ;
        TrieNode cur = root ;
        TrieNode chs1[] = cur.chs ;
        for(int i = 0 ; i < arr.length ; i ++) {
            if(chs1[arr[i]-'a'] == null) {
                chs1[arr[i]-'a'] = new TrieNode() ;
                chs1[arr[i]-'a'].count = 1 ;
            } else {
                chs1[arr[i]-'a'].count ++ ; 
            }
            if(i == arr.length - 1) {
                chs1[arr[i]-'a'].isEnd = true ;
                chs1[arr[i]-'a'].word = word ;
            } else {
                chs1 = chs1[arr[i]-'a'].chs ;//向下层迭代
            }
        }
    }
    
    public void delete(String word) {
        if(!search(word)) return ;
        char[] arr = word.toCharArray() ;
        TrieNode cur = root ;
        TrieNode chs1[] = cur.chs ;
        for(int i = 0 ; i < arr.length ; i ++) {    
            chs1[arr[i]-'a'].count -- ;
            if(chs1[arr[i]-'a'].count == 0) {
                chs1[arr[i]-'a'] = null ;
                return ;
            }
            if(i == arr.length - 1) {
                chs1[arr[i]-'a'].isEnd = false ;
                chs1[arr[i]-'a'].word = null ;
            } else {
                chs1 = chs1[arr[i]-'a'].chs ;
            }
            
        }
    }
    
    public boolean search(String word) {
        TrieNode cur = root ;
        char[] arr = word.toCharArray() ;
        TrieNode chs1[] = cur.chs ;
        for(int i = 0 ; i < arr.length ; i ++) {
            if(chs1[arr[i]-'a'] == null) return false ;
            if(i == arr.length-1 && chs1[arr[i]-'a'].isEnd == true) return true ;
            chs1 = chs1[arr[i]-'a'].chs ;
        }
        return false ;
    }
    
    public int prefixNumber(String pre) {
        TrieNode cur = root ;
        char[] arr = pre.toCharArray() ;
        TrieNode chs1[] = cur.chs ;
        for(int i = 0 ; i < arr.length ; i ++) {
            if(chs1[arr[i]-'a'] == null) return 0 ;
            if(i == arr.length - 1) return chs1[arr[i]-'a'].count ;
            chs1 = chs1[arr[i]-'a'].chs ;
        }
        return 0 ;
    }
}