LeetCode Implement Trie (Prefix Tree)

원제 링크 는 다음 과 같 습 니 다:https://leetcode.com/problems/implement-trie-prefix-tree/
Trie 는 사전 검색 에 사용 되 는 데이터 구조 로 빠 른 검색 에 사용 되 는 다 차원 구조 이다.예 를 들 어 영문 자모의 사전 나 무 는 26 갈래 이 고 숫자의 사전 나 무 는 10 갈래 나무 이다. 
Trie 나무의 기본 적 인 성질 은 세 가지 가 있 는데 요약 하면:
4. 567917. 뿌리 노드 는 문 자 를 포함 하지 않 고 뿌리 노드 이외 의 모든 노드 는 하나의 문자 만 포함 합 니 다
4. 567917. 뿌리 노드 에서 특정한 노드 까지 경로 에 있 는 문자 가 연결 되 어 이 노드 에 대응 하 는 문자열 입 니 다
4. 567917. 각 노드 의 모든 하위 노드 에 포 함 된 문자열 이 다 릅 니 다
다음은 두 가지 방법 이 있 는데, 첫 번 째 는 상대 적 으로 간결 하 다.
AC Java:

 1 class TrieNode {
 2     String val = "";
 3     TrieNode [] nexts; 
 4     
 5     public TrieNode() {
 6         nexts = new TrieNode[26];
 7     }
 8 }
 9 
10 public class Trie {
11     private TrieNode root;
12     
13     public Trie() {
14         root = new TrieNode();
15     }
16 
17     // Inserts a word into the trie.
18     public void insert(String word) {
19         TrieNode p = root;
20         for(char c : word.toCharArray()){
21             if(p.nexts[c-'a'] == null){
22                 p.nexts[c-'a'] = new TrieNode();
23             }
24             p = p.nexts[c-'a'];
25         }
26         p.val = word;
27     }
28 
29     // Returns if the word is in the trie.
30     public boolean search(String word) {
31         TrieNode p = root;
32         for(char c : word.toCharArray()){
33             if(p.nexts[c-'a'] == null){
34                 return false;
35             }
36             p = p.nexts[c-'a'];
37         }
38         return p.val.equals(word);
39     }
40 
41     // Returns if there is any word in the trie
42     // that starts with the given prefix.
43     public boolean startsWith(String prefix) {
44         TrieNode p = root;
45         for(char c : prefix.toCharArray()){
46             if(p.nexts[c-'a'] == null){
47                 return false;
48             }
49             p = p.nexts[c-'a'];
50         }
51         return true;
52     }
53 }

두 번 째 방법 은 잎 노드 인지 아 닌 지 를 사용 하 는 것 이다.첫 번 째 방법의 저장 val 과 는 다 르 지만 본질 적 으로 는 동일 하 다.
참고: search () 와 starts With () 는 다 릅 니 다. search 는 loop 에서 뛰 어 내 릴 때 Trie 나무의 잎 노드 가 있 는 지 주의해 야 합 니 다.
AC Java:

 1 class TrieNode {
 2     //Mark if this node is the end of the word
 3     boolean isLeaf;
 4     HashMap<Character,TrieNode> nexts;
 5     public TrieNode() {
 6         nexts = new HashMap<Character,TrieNode>();
 7     }
 8 }
 9 
10 public class Trie {
11     private TrieNode root;
12     
13     public Trie() {
14         root = new TrieNode();
15     }
16 
17     // Inserts a word into the trie.
18     public void insert(String word) {
19         TrieNode p = root;
20         char [] s = word.toCharArray();
21         int len = s.length;
22         int i = 0;
23         //traverse the existing character
24         while(i<len){
25             if(p.nexts.containsKey(s[i])){
26                 p = p.nexts.get(s[i]);
27                 i++;
28             }else{
29                 break;
30             }
31         }
32         //append new nodes
33         while(i<len){
34             TrieNode newNode = new TrieNode();
35             p.nexts.put(s[i],newNode);
36             p = newNode;
37             i++;
38         }
39         //Set the end of the word
40         p.isLeaf = true;
41     }
42 
43     // Returns if the word is in the trie.
44     public boolean search(String word) {
45         TrieNode p = root;
46         char [] s = word.toCharArray();
47         int len = s.length;
48         int i = 0;
49         while(i<len){
50             TrieNode nextNode = p.nexts.get(s[i]);
51             if(nextNode == null){
52                 return false;
53             }
54             p = nextNode;
55             i++;
56         }
57         //return if this is a leaf node
58         return p.isLeaf;
59     }
60 
61     // Returns if there is any word in the trie
62     // that starts with the given prefix.
63     public boolean startsWith(String prefix) {
64         TrieNode p = root;
65         char [] s = prefix.toCharArray();
66         int len = s.length;
67         int i = 0;
68         while(i<len){
69             TrieNode nextNode = p.nexts.get(s[i]);
70             if(nextNode == null){
71                 return false;
72             }
73             p = nextNode;
74             i++;
75         }
76         return true;
77     }
78 }
79 
80 // Your Trie object will be instantiated and called as such:
81 // Trie trie = new Trie();
82 // trie.insert("somestring");
83 // trie.search("key");

이 댓 글 을 참고 하 였 습 니 다.http://blog.csdn.net/wzy_1988 / article / details / 45744067 \ # trie 트 리 기본 구현