前缀树

Leetcode208

208. 实现 Trie (前缀树)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

TrieNode

随着数据的不断插入，根据需要不断创建 TrieNode 节点。

class Trie {

    public class TrieNode{
        boolean end;
        TrieNode[] arr = new TrieNode[26];
    }

    TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); i++){
            int val = word.charAt(i) - 'a';
            if(node.arr[val] == null)node.arr[val] = new TrieNode();
            node = node.arr[val];
        }
        node.end = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); i++){
            int val = word.charAt(i) - 'a';
            if(node.arr[val] == null)return false;
            node = node.arr[val];
        }
        return node.end;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for(int i = 0; i < prefix.length(); i++){
            int val = prefix.charAt(i) - 'a';
            if(node.arr[val] == null)return false;
            node = node.arr[val];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

二维数组

class Trie {
    int N = 100009;
    int[][] trie;
    boolean[] end;//记录某个格子是否被标记为末尾
    int index;//自增记录我们到底用了多少个格子

    public Trie() {
        trie = new int[N][26];
        end = new boolean[N];
        index = 0;
    }

    public void insert(String word) {
        int x = 0;
        for(int i = 0; i < word.length(); i++){
            int y = word.charAt(i) - 'a';
            if(trie[x][y] == 0)trie[x][y] = ++index;
            x = trie[x][y];
        }
        end[x] = true;
    }

    public boolean search(String word) {
        int x = 0;
        for(int i = 0; i < word.length(); i++){
            int y = word.charAt(i) - 'a';
            if(trie[x][y] == 0)return false;
            x = trie[x][y];
        }
        return end[x];
    }

    public boolean startsWith(String prefix) {
        int x = 0;
        for(int i = 0; i < prefix.length(); i++){
            int y = prefix.charAt(i) - 'a';
            if(trie[x][y] == 0)return false;
            x = trie[x][y];
        }
        return true;
    }
}

两种方式的对比

使用「二维数组」的好处是写起来飞快，同时没有频繁 new 对象的开销。但是需要根据数据结构范围估算我们的「二维数组」应该开多少行。

坏处是使用的空间通常是「TrieNode」方式的数倍，而且由于通常对行的估算会很大，导致使用的二维数组开得很大，如果这时候每次创建 Trie 对象时都去创建数组的话，会比较慢，而且当样例多的时候甚至会触发 GC（因为 OJ每测试一个样例会创建一个 Trie 对象）。

因此还有一个小技巧是将使用到的数组转为静态，然后利用 index 自增的特性在初始化 Trie 时执行清理工作 & 重置逻辑。

这样的做法能够使评测时间降低一半，运气好的话可以得到一个与「TrieNode」方式差不多的时间。

class Trie {
    // 以下 static 成员独一份，被创建的多个 Trie 共用
    static int N = 100009; // 直接设置为十万级
    static int[][] trie = new int[N][26];
    static int[] count = new int[N];
    static int index = 0;

    // 在构造方法中完成重置 static 成员数组的操作
    // 这样做的目的是为减少 new 操作（无论有多少测试数据，上述 static 成员只会被 new 一次）
    public Trie() {
        for (int row = index; row >= 0; row--) {
            Arrays.fill(trie[row], 0);
        }
        Arrays.fill(count, 0);
        index = 0;
    }

    public void insert(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) trie[p][u] = ++index;
            p = trie[p][u];
        }
        count[p]++;
    }

    public boolean search(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) return false;
            p = trie[p][u];
        }
        return count[p] != 0;
    }

    public boolean startsWith(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (trie[p][u] == 0) return false;
            p = trie[p][u];
        }
        return true;
    }
}

关于 Trie 的应用面

首先，在纯算法领域，前缀树算是一种较为常用的数据结构。

不过如果在工程中，不考虑前缀匹配的话，基本上使用 hash 就能满足。

如果考虑前缀匹配的话，工程也不会使用 Trie 。

一方面是字符集大小不好确定（题目只考虑 26 个字母，字符集大小限制在较小的 26 内）因此可以使用 Trie，但是工程一般兼容各种字符集，一旦字符集大小很大的话，Trie 将会带来很大的空间浪费。

另外，对于个别的超长字符 Trie 会进一步变深。

这时候如果 Trie 是存储在硬盘中，Trie 结构过深带来的影响是多次随机 IO，随机 IO 是成本很高的操作。

同时 Trie 的特殊结构，也会为分布式存储将会带来困难。

因此在工程领域中 Trie 的应用面不广。

至于一些诸如「联想输入」、「模糊匹配」、「全文检索」的典型场景在工程主要是通过 ES (ElasticSearch) 解决的。

而 ES 的实现则主要是依靠「倒排索引」 ~

转载链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/gong-shui-san-xie-yi-ti-shuang-jie-er-we-esm9/

栗子：Leetcode421

421. 数组中两个数的最大异或值

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

进阶：你可以在 O（n） 的时间解决这个问题吗？

class Solution {
    public class TrieNode{
        TrieNode left;
        TrieNode right;
    }
    TrieNode root = new TrieNode();
    public void insert(int x){
        TrieNode p = root;
        for(int i = 31; i >= 0; i--){
            int u = (x >> i) & 1;
            if(u == 0){
                if(p.left == null)p.left = new TrieNode();
                p = p.left;
            }else{
                if(p.right == null)p.right = new TrieNode();
                p = p.right;
            }
        }
    }

    public int getVal(int x){
        TrieNode p = root;
        int ret = 0;
        for(int i = 31; i >= 0; i--){
            int a = (x >> i) & 1, b = 1 -a;
            if(b == 0){
                if(p.left != null){
                    ret |= (b << i);
                    p = p.left;
                }else{
                    ret |= (a << i);
                    p = p.right;
                }
            }else{
                if(p.right != null){
                    ret |= (b << i);
                    p = p.right;
                }else{
                    ret |= (a << i);
                    p = p.left;
                }
            }
        }
        return ret;
    }
    public int findMaximumXOR(int[] nums) {
        int ret = 0;
        insert(nums[0]);
        for(int i = 1; i < nums.length; i++){
            insert(nums[i]);
            int j = getVal(nums[i]);
            ret = Math.max(ret,nums[i] ^ j);
        }
        return ret;
    }
}