1+ // 208. 实现 Trie (前缀树)
2+
3+
4+ /**
5+ * Your Trie object will be instantiated and called as such:
6+ * Trie obj = new Trie();
7+ * obj.insert(word);
8+ * boolean param_2 = obj.search(word);
9+ * boolean param_3 = obj.startsWith(prefix);
10+ */
11+
12+
13+ /*
14+ 前缀树：
15+ 1、创建前缀结点内部类 TrieNode
16+ 1）成员变量 isEnd 表示结点是否叶子结点，用于搜索时判断是否搜索结束
17+ 2）字母映射表 next 保存了对当前结点而言下一个可能出现的所有字符的引用，因此可以通过一个父结点来预知它所有子结点的值
18+ Trie 中一般都含有大量的空引用，因此在绘制一棵单词查找树时一般会忽略空引用
19+ 3）构造函数，对成员变量 isEnd、next 赋值初始化
20+ 2、设计前缀树
21+ 1）成员变量前缀结点 root，作为单词树的入口，方便构造和查找
22+ 2）构造函数对成员变量root初始化
23+ 3）插入：向 Trie 中插入一个单词 word
24+ 这个操作和构建链表很像。首先从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，
25+ 这时开始不断创建新的结点，直到插入完 word 的最后一个字符，同时还要标记最后一个结点 isEnd=true，表示它是一个单词的末尾
26+ 4）单词查找：查找 Trie 中是否存在单词 word
27+ 从根结点的子结点开始，一直向下匹配，如果出现结点值为空就返回 false，如果匹配到了最后一个字符，再判断结点是否单词末尾返回是否存在单词
28+ 5）前缀查找：判断 Trie 中是否有以 prefix 为前缀的单词
29+ 和 search 操作类似，但只要匹配到最后一个字符，就说明存在该前缀的单词
30+
31+ sea、sell、she
32+ s
33+ / \
34+ e h
35+ / \ |
36+ a l e
37+ |
38+ l
39+ */
40+ class Trie {
41+
42+ class TrieNode {
43+ private boolean isEnd ;
44+ private TrieNode [] next ;
45+
46+ public TrieNode () {
47+ isEnd = false ;
48+ next = new TrieNode [26 ];
49+ }
50+ }
51+
52+ private TrieNode root ;
53+
54+ public Trie () {
55+ root = new TrieNode ();
56+ }
57+
58+ public void insert (String word ) {
59+ TrieNode node = root ;
60+ for (char c : word .toCharArray ()) {
61+ if (node .next [c - 'a' ] == null ) {
62+ node .next [c - 'a' ] = new TrieNode ();
63+ }
64+ node = node .next [c - 'a' ];
65+ }
66+ node .isEnd = true ;
67+ }
68+
69+ public boolean search (String word ) {
70+ TrieNode node = root ;
71+ for (char c : word .toCharArray ()) {
72+ node = node .next [c - 'a' ];
73+ if (node == null ) {
74+ return false ;
75+ }
76+ }
77+ return node .isEnd ;
78+ }
79+
80+ public boolean startsWith (String prefix ) {
81+ TrieNode node = root ;
82+ for (char c : prefix .toCharArray ()) {
83+ node = node .next [c - 'a' ];
84+ if (node == null ) {
85+ return false ;
86+ }
87+ }
88+ return true ;
89+ }
90+ }
0 commit comments