稀有猿诉

十年磨一剑，历炼出锋芒，说话千百句，不如码二行。

Introduction to Trie

字典树，Trie（发音与try一样），也叫前缀树，是在一个树状数据结构中存储一个字典中的所有单词，以快速的实现前缀搜索和单词搜索的数据结构。前缀树是一个多叉树，每个节点会有多个子节点，具体子节点 数量取决于字符集的大小，除了根节点以外，每个节点代表字典中的一个字符，从根节点开始的路径代表着一个前缀或者一个单词。

Trie通常用于解决单词搜索和前缀匹配一类的问题，特点是输入的字符集合有限（通常是仅有小写字母），给一组字符串作为输入字典（这就是字典），然后涉及前缀或者单词搜索，符合这几个条件的问题就可以考虑使用Trie来解决。

Trie的标准实现

标准的Trie是一个树形结构，其节点是TrieNode，有一个构建字典方法通常是插入一个字符串，以及查询方法search通常是一个完整单词，还有一个前缀查询方法startsWith。

节点的实现，对于大多数情况下依据字符集而定，通常情况下都是只有小写英文字符，所以用一个长度为26的数组即可，因为是树状，要能找到子节点，所以这个数组的类型仍是TrieNode，下标可以作为当前节点的字符。同时可以添加额外的字段 用以标记，到当前节点是否是一个完整单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class Trie {
    private static class TrieNode {
        TrieNode[] children;
        boolean isWord;

        TrieNode() {
            children = new TrieNode[26];
            isWord = false;
        }
    }

    private TrieNode root;

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

    public void insert(String word) {
        if (word == null || word.length() == 0) {
            return;
        }
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int idx = ch - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        if (word == null || word.length() == 0) {
            return false;
        }
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int idx = ch - 'a';
            if (node.children[idx] == null) {
                return false;
            }
            node = node.children[idx];
        }
        return node.isWord;
    }

    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) {
            return false;
        }
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            int idx = ch - 'a';
            if (node.children[idx] == null) {
                return false;
            }
            node = node.children[idx];
        }

        return true;
    }
}

解题技巧

对于标准实现中，每个节点只有一个额外的字段用以标记到此节点时的路径是否是一个单词。

其实这里也可以加入更多的字段，比如输入字符串携带的其他信息，这样当搜索时遇到匹配，就可以直接提取出这些额外的信息，较复杂的问题必然有单词匹配或者前缀匹配以外的信息需要融合，这时节点就需要多定义一些字段。最为典型的就是题745。

典型问题

题目 题解 说明
14. 最长公共前缀 题解
208. 实现 Trie (前缀树) 题解
211. 添加与搜索单词 - 数据结构设计 题解 搜索时用DFS
648. 单词替换 题解
676. 实现一个魔法字典 题解
745. 前缀和后缀搜索 题解
题解
题解
题解

参考资料

Comments