【Leetcode 热题 100】208. 实现 Trie (前缀树)

题目配景

                                    T                         r                         i                         e                              Trie                  Trie 或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据会合的键。这一数据结构有相当多的应用情景，例如主动补全和拼写检查。
请你实现 Trie 类：

• Trie() 初始化前缀树对象。
  
• void insert(String word) 向前缀树中插入字符串                                         w                            o                            r                            d                                  word                     word。
  
• boolean search(String word) 如果字符串                                         w                            o                            r                            d                                  word                     word 在前缀树中，返回                                         t                            r                            u                            e                                  true                     true（即，在检索之前已经插入）；否则，返回                                         f                            a                            l                            s                            e                                  false                     false。
  
• boolean startsWith(String prefix) 如果之前已经插入的字符串                                         w                            o                            r                            d                                  word                     word 的前缀之一为                                         p                            r                            e                            f                            i                            x                                  prefix                     prefix，返回                                         t                            r                            u                            e                                  true                     true；否则，返回                                         f                            a                            l                            s                            e                                  false                     false。
  

数据束缚

•                                         1                            ≤                            w                            o                            r                            d                            .                            l                            e                            n                            g                            t                            h                            ,                            p                            r                            e                            f                            i                            x                            .                            l                            e                            n                            g                            t                            h                            ≤                            2000                                  1 \le word.length, prefix.length \le 2000                     1≤word.length,prefix.length≤2000
  
•                                         w                            o                            r                            d                                  word                     word 和                                         p                            r                            e                            f                            i                            x                                  prefix                     prefix 仅由小写英笔墨母组成
  
• insert、search 和 startsWith 调用次数 总计 不超过                                         3                            ×                            1                                       0                               4                                            3 \times 10 ^ 4                     3×104 次
  

解题过程

前缀树模板题，要求实现的功能比力范围且数据范围不是很大，用类界说就可以。
这种做法必要在每个树节点中开一个长度和字符种类同等的数组，本题中表现为                                   26                              26                  26叉树，当数据量很大时，冗余的空间会膨胀得很厉害。
还有一种使用静态二维数组的写法，但是测试用例之间必要清空数组，和这道题的提交方式有点辩论，等遇到要用的时间再练习。
具体实现

1. class TreeNode {
2.     TreeNode[] path = new TreeNode[26];
3.     boolean end;
4. }
6. class Trie {
7.     private TreeNode root;
9.     public Trie() {
10.         root = new TreeNode();
11.     }
12.    
13.     public void insert(String word) {
14.         TreeNode cur = root;
15.         for(char c : word.toCharArray()) {
16.             c -= 'a';
17.             // 如果当前字符位置不存在路径，那么给它简历一个新结点
18.             if(cur.path[c] == null) {
19.                 cur.path[c] = new TreeNode();
20.             }
21.             // 移动工作指针
22.             cur = cur.path[c];
23.         }
24.         cur.end = true;
25.     }
26.    
27.     public boolean search(String word) {
28.         return find(word) == 1;
29.     }
30.    
31.     public boolean startsWith(String prefix) {
32.         return find(prefix) != 0;
33.     }
35.     private int find(String word) {
36.         TreeNode cur = root;
37.         for(char c : word.toCharArray()) {
38.             c -= 'a';
39.             if(cur.path[c] == null) {
40.                 return 0;
41.             }
42.             cur = cur.path[c];
43.         }
44.         // 返回 1 表示这个单词在此结束，2 表示这个字母不是单词的结尾
45.         return cur.end ? 1 : 2;
46.     }
47. }
49. /**
50. * Your Trie object will be instantiated and called as such:
51. * Trie obj = new Trie();
52. * obj.insert(word);
53. * boolean param_2 = obj.search(word);
54. * boolean param_3 = obj.startsWith(prefix);
55. */

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。