题解 | 字典树的实现(静态数组)

import java.io.*;

/**
 * @author cat
 * @description https://www.nowcoder.com/practice/7f8a8553ddbf4eaab749ec988726702b
 * @create 2025/7/14 09:02
 * @since JDK17
 */

class Trie {
    int MAXN = 150001;
    int[][] tree = new int[MAXN][26];
    int cnt = 1;
    int[] ends = new int[MAXN];
    int[] pass = new int[MAXN];

    public void insert(String word) {
        int cur = 1;
        pass[cur]++;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
            pass[cur]++;
        }
        ends[cur]++;
    }

    public Trie() {
        cnt = 1;
    }

    public void delete (String word) {
        if (search(word) > 0) { // 必须得先存在
            int cur = 1;
            for (int i = 0; i < word.length(); i++) {
                int path = word.charAt(i) - 'a';
                int nextNode = tree[cur][path];
                if (--pass[nextNode] == 0) {    //
                    tree[cur][path] = 0;
                    return;
                }
                cur = nextNode;
            }
            ends[cur]--;
        }
    }

    public int find(String word) {
        int cur = 1;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) { // 不存在
                return -1;
            }
            cur = tree[cur][path];
        }
        return cur;
    }

    public int search(String word) {
        int cur = find(word);
        return cur != -1 ? ends[cur] : -1;
    }

    public int prefixNumber(String word) {
        int cur = find(word);
        return cur != -1 ? pass[cur] : 0;
    }
}
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pr = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer st = new StreamTokenizer(br);
    static Trie trie = new Trie();

    public static void main(String[] args) throws IOException {
        trie.cnt = 1;
        st.nextToken();
        int n = ((int) st.nval);
        for (int i = 0; i < n; i++) {
            st.nextToken();
            int opt = ((int) st.nval);
            st.nextToken();
            String word = ((String) st.sval);
            if (opt == 1) {
                trie.insert(word);
            } else if (opt == 2) {
                trie.delete(word);
            } else if (opt == 3) {
                pr.println(trie.search(word) <= 0 ? "NO" : "YES");
            } else {
                pr.println(trie.prefixNumber(word));
            }
        }
        pr.flush();
        pr.close();
        br.close();
    }
}