题解 | 字典树的实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU (String[][] operators) {
        List<String> res = new ArrayList<>();
        for(String[] op: operators) {
            String type = op[0];
            String word = op[1];
            if(type.equals("1")) {
                insert(word);
            } else if(type.equals("2")) {
                delete(word);
            } else if(type.equals("3")) {
                res.add(search(word) ? "YES" : "NO");
            } else if(type.equals("4")) {
                res.add(String.valueOf(prefixNUmber(word)));
            }
        }
        return res.toArray(new String[0]);
    }



    class TrieNode {
        public int pass;
        public int end;
        public TrieNode[] nexts;

        public TrieNode() {
            pass = 0;
            end = 0;
            nexts = new TrieNode[26];
        }
    }

    private TrieNode root;

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

    public void insert(String word) {
        TrieNode node = root;
        node.pass++;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (node.nexts[path] == null) {
                node.nexts[path] = new TrieNode();
            }
            node = node.nexts[path];
            node.pass++;
        }
        node.end++;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (node.nexts[path] == null) {
                return false;
            }
            node = node.nexts[path];
        }
        if (node.end > 0) {
            return true;
        }
        return false;

    }

    public void delete (String word) {
        if (search(word) == false) {
            return;
        }
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            node.pass--;
            node = node.nexts[path];
        }
        node.end--;
    }

    public int prefixNUmber(String pre) {
        TrieNode node = root;
        int num = 0;
        for (int i = 0; i < pre.length(); i++) {
            int path = pre.charAt(i) - 'a';
            if (node.nexts[path] == null) {
                return 0;
            }
            node = node.nexts[path];
        }
        num = node.pass;
        return num;
    }
}