题解 | #字典树的实现#

import java.util.*;


public class Solution {

    public class TrieNode {
        public int pre;
        public int end;
        public TrieNode[] paths;
        public TrieNode() {
            pre = 0;
            end = 0;
            paths = new TrieNode[26];
        }
    }

    public class Trie {
        private TrieNode root;
        public Trie() {
            root = new TrieNode();
        }
        // 添加 word，可重复添加
        public void insert(String word) {
            if (null == word) {
                return;
            }
            char[] chrs = word.toCharArray();
            TrieNode node = root;
            node.pre++;
            int index = 0;
            for (int i = 0; i < chrs.length; i++) {
                index = chrs[i] - 'a';
                if (null == node.paths[index]) {
                    node.paths[index] = new TrieNode();
                }
                node = node.paths[index];
                node.pre++;
            }
            node.end++;
        }
        // 删除 word，如果 word 添加过多次，仅删除一次
        public void delete (String word) {
            if (search(word)) {
                char[] chrs = word.toCharArray();
                TrieNode node = root;
                node.pre--;
                int index = 0;
                for (int i = 0; i < chrs.length; i++) {
                    index = chrs[i] - 'a';
                    if (--node.paths[index].pre == 0) {
                        node.paths[index] = null;
                        return;
                    }
                    node = node.paths[index];
                }
                node.end--;
            }
        }
        // 查询 word 是否在字典树中出现过(完整的出现过，前缀式不算)
        public boolean search(String word) {
            if (null == word) {
                return false;
            }
            char[] chrs = word.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (int i = 0; i < chrs.length; i++) {
                index = chrs[i] - 'a';
                if (null == node.paths[index]) {
                    return false;
                }
                node = node.paths[index];
            }
            return node.end > 0 ? true : false;
        }
        // 返回以字符串 pre 作为前缀的单词数量
        public int prefixNumber(String pre) {
            if (null == pre) {
                return 0;
            }
            char[] chrs = pre.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (int i = 0; i < chrs.length; i++) {
                index = chrs[i] - 'a';
                if (null == node.paths[index]) {
                    return 0;
                }
                node = node.paths[index];
            }
            return node.pre;
        }
    }

    /**
     *
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU (String[][] operators) {
        // write code here

        if (0 == operators.length) {
            return new String[] {};
        }

        Trie trie = new Trie();
        ArrayList<String> rs = new ArrayList<>();

        for (String[] operator : operators) {
            int op = Integer.valueOf(operator[0]);
            String str = operator[1];
            switch (op) {
                case 1:
                    trie.insert(str);
                    break;
                case 2:
                    trie.delete(str);
                    break;
                case 3 :
                    boolean bool = trie.search(str);
                    if (bool) {
                        rs.add("YES");
                    } else {
                        rs.add("NO");
                    }
                    break;
                default:
                    int num = trie.prefixNumber(str);
                    rs.add(String.valueOf(num));
            }
        }

        String[] strs = new String[rs.size()];
        for (int i = 0; i < strs.length; i++) {
            strs[i] = rs.get(i);
        }

        return strs;
    }
}