Trie 树

树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。

其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。

IMG_1659.PNG

数组实现 Trie

一个朴素的想法是直接使用「二维数组」来实现 树。

由于题目要求我们实现删除操作，因此我们需要额外开一个 cnt 数组用于记录某个字符出现次数。

与此同时，我们可以设计一个同时支持 写入/删除 的函数 insert：

  • 写入 s 时，调用 insert(s, 1)；
  • 删除 s 时，调用 insert(s, -1)。

综上，数组实现 我们一共需要如下属性：

  • 使用二维数组 来存储我们所有的单词字符；
  • 使用 来自增记录我们到底用了多少个格子（相当于给被用到格子进行编号）；
  • 使用 数组记录某个格子被「被标记的次数」（当 编号的格子被标记了 次，则有 ）；
  • 使用 数组记录记录某个格子被「被标记为结尾的次数」。

代码：

import java.util.*;

public class Solution {
    class Trie {
        int N = 1000009;
        int[][] tr = new int[N][26];
        int[] cnt = new int[N];
        int[] isWord = new int[N];
        int idx = 0;

        void insert(String s, int v) {
            int p = 0;
            for (int i = 0; i < s.length(); i++) {
                int u = s.charAt(i) - 'a';
                if (tr[p][u] == 0) tr[p][u] = ++idx;
                p = tr[p][u];
                cnt[p] += v;
            }
            isWord[p] += v;
        }

        boolean search(String s) {
            int p = 0;
            for (int i = 0; i < s.length(); i++) {
                int u = s.charAt(i) - 'a';
                if (cnt[tr[p][u]] == 0) return false;
                p = tr[p][u];
            }
            return isWord[p] > 0;
        }

        int prefixNumber(String s) {
            int p = 0;
            for (int i = 0; i < s.length(); i++) {
                int u = s.charAt(i) - 'a';
                if (cnt[tr[p][u]] == 0) return 0;
                p = tr[p][u];
            }
            return cnt[p];
        }
    }
    Trie trie = new Trie();
    public String[] trieU (String[][] operators) {
        List<String> list = new ArrayList<>();
        for (String[] cur : operators) {
            if (cur[0].equals("1")) {
                trie.insert(cur[1], 1);
            } else if (cur[0].equals("2")) {
                trie.insert(cur[1], -1);
            } else if (cur[0].equals("3")) {
                list.add(trie.search(cur[1]) ? "YES" : "NO");
            } else if (cur[0].equals("4")) {
                list.add(String.valueOf(trie.prefixNumber(cur[1])));
            }
        }
        int m = list.size();
        String[] ans = new String[m];
        for (int i = 0; i < m; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
}

最后

这是我们「必考真题 の 精选」系列文章的第 No.124 篇，系列开始于 2021/07/01。

该系列会将牛客网中「题霸 - 面试必考真题」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)