当前位置：首页 > news >正文

LeetCode——Implement Trie (Prefix Tree)

news 来源：原创 2024/5/7 6:07:18

Description：

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

实现一个简单的Trie树，参考我的博客：http://www.cnblogs.com/wxisme/p/4876197.html

 1 class TrieNode {
 2     public TrieNode[] son;
 3     public boolean isEnd;
 4     // Initialize your data structure here.
 5     public TrieNode() {
 6         this.son = new TrieNode[26];
 7         isEnd = false;
 8         
 9     }
10 }
11 
12 public class Trie {
13     private TrieNode root;
14 
15     public Trie() {
16         root = new TrieNode();
17     }
18 
19     // Inserts a word into the trie.
20     public void insert(String word) {
21         char[] wordChars = word.toCharArray();
22         TrieNode node = this.root;
23         for(char ch : wordChars) {
24             int pos = ch - 'a';
25             if(node.son[pos] == null) {
26                 node.son[pos] = new TrieNode();
27             }
28             node = node.son[pos];
29         }
30         node.isEnd = true;
31     }
32 
33     // Returns if the word is in the trie.
34     public boolean search(String word) {
35         char[] wordChars = word.toCharArray();
36         TrieNode node = this.root;
37         for(char ch : wordChars) {
38             int pos = ch - 'a';
39             if(node.son[pos] == null) {
40                 return false;
41             }
42             node = node.son[pos];
43         }
44         return node.isEnd;
45     }
46 
47     // Returns if there is any word in the trie
48     // that starts with the given prefix.
49     public boolean startsWith(String prefix) {
50         
51         char[] prefixChars = prefix.toCharArray();
52         TrieNode node = this.root;
53         for(char ch : prefixChars) {
54             int pos = ch - 'a';
55             if(node.son[pos] == null) {
56                 return false;
57             }
58             node = node.son[pos];
59         }
60         return true;
61     }
62 }
63 
64 // Your Trie object will be instantiated and called as such:
65 // Trie trie = new Trie();
66 // trie.insert("somestring");
67 // trie.search("key");