Preface
Trie
(发音类似 try)前缀树,一种树形数据结构,用于高效地存储和检索字符串数据集中的键,
有相当多地应用情景:自动补全和拼写检查,又称为字典树,实质上是 N叉树 的一种特殊形式。
相关题目推荐:
还有一道比较经典的题目:求数组中的最大异或值。
Solution
结点形式实现代码:
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
| class Trie { private Trie[] children; private boolean isEnd;
public Trie() { children = new Trie[26]; isEnd = false; } public void insert(String word) { Trie node = this; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { node.children[index] = new Trie(); } node = node.children[index]; } node.isEnd = true; } public boolean search(String word) { Trie node = searchPrefix(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; }
private Trie searchPrefix(String prefix) { Trie node = this; for (int i = 0; i < prefix.length(); i++) { char ch = prefix.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { return null; } node = node.children[index]; } return node; } }
|
数组形式实现代码:
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
| class Main { static int N = 100010; static int[][] son = new int[N][26]; static int[] cnt = new int[N]; static int idx = 0; public static void insert(String s) { int p = 0; for (int i = 0; i < s.length(); i++) { int t = s.charAt(i) - 'a'; if (son[p][t] == 0) { son[p][t] = ++idx; } p = son[p][t]; } cnt[p]++; } public static int query(String s) { int p = 0; for (int i = 0; i < s.length(); i++) { int t = s.charAt(i) - 'a'; if (son[p][t] == 0) { return 0; } p = son[p][t]; } return cnt[p]; } }
|
文章开始处的两个链接,前者直接应用到字典树,而后者间接用到字典树,
都给出了非常巧妙地解法,尤其是后者如何层序遍历得出字典树结点数目,非常精彩。