NC124 字典树的实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU (String[][] operators) {
        // write code here
        List<String> res = new ArrayList<>();
        Trie tree = new Trie();
        for(int i = 0;i < operators.length;++i){
            switch(operators[i][0]){
                    // 插入
                case "1":
                    tree.insert(operators[i][1]);
                    break;
                    // 删除
                case "2":
                    tree.delete(operators[i][1]);
                    break;
                    // 查找单词
                case "3":
                    res.add(tree.search(operators[i][1]));
                    break;
                    // 查找前缀
                case "4":
                    res.add(String.valueOf(tree.prefixNumber(operators[i][1])));
                    break;
            }
        }
        String[] ans = new String[res.size()];
        for (int i = 0;i < ans.length;++i){
            ans[i] = res.get(i);
      }
      return ans;
    }
    class Trie {
        class TrieNode{
            int end;
            int prefix;
            char ch;
            TrieNode[] next = new TrieNode[26];
            public TrieNode (){
                end = 0;
                prefix = 0;
            }
        }

        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word){
            TrieNode p = root;
            for(int i=0;i<word.length();i++){
                int index = word.charAt(i) - 'a';
                if(p.next[index] == null) p.next[index] = new TrieNode();
                p.prefix++;
                p = p.next[index];
                p.ch = word.charAt(i);
            }// 结尾处理
            p.prefix++;
            p.end ++;
        }

        public void delete(String word){
            TrieNode p = root;
            for(int i=0;i<word.length();i++){
                int index = word.charAt(i) - 'a';
                TrieNode cur = p.next[index];
                cur.prefix--;
                if(cur.prefix == 0){ // 空了直接删除后续节点 break
                    p.next[index] = null;
                    break;
                }
                p = p.next[index];
            }

        }
        public String search(String word){
            TrieNode p = root;
            TrieNode cur = null;
            int i=0;
            for(;i<word.length();i++){
                int index = word.charAt(i) - 'a';
                cur = p.next[index];
                // 判断的顺序也很重要 先判断是否为空 否则会报错
                if(p.next[index] != null && cur.prefix != 0 ) p = p.next[index];
                else break;
            }
            if(i == word.length() && cur.end != 0 ) return "YES";
            else return "NO";
        }

        public int prefixNumber(String pre){
            TrieNode p = root;
            TrieNode cur = null;
            int i = 0;
            for(;i<pre.length();i++){
                int index = pre.charAt(i) - 'a';
                cur = p.next[index];
                if(p.next[index] != null && cur.prefix != 0 ) p = p.next[index];
                else break;
            }
            if(i == pre.length() ) return p.prefix;
            else return 0;

        }
    }
}