208. Implement Trie (Prefix Tree) Medium

1/**
2 * [208] Implement Trie (Prefix Tree)
3 *
4 * A <a href="https://en.wikipedia.org/wiki/Trie" target="_blank">trie</a> (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
5 * Implement the Trie class:
6 * 
7 * 	Trie() Initializes the trie object.
8 * 	void insert(String word) Inserts the string word into the trie.
9 * 	boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
10 * 	boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
11 * 
12 *  
13 * Example 1:
14 * 
15 * Input
16 * ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
17 * [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
18 * Output
19 * [null, null, true, false, true, null, true]
20 * Explanation
21 * Trie trie = new Trie();
22 * trie.insert("apple");
23 * trie.search("apple");   // return True
24 * trie.search("app");     // return False
25 * trie.startsWith("app"); // return True
26 * trie.insert("app");
27 * trie.search("app");     // return True
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	1 <= word.length, prefix.length <= 2000
33 * 	word and prefix consist only of lowercase English letters.
34 * 	At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/implement-trie-prefix-tree/
40// discuss: https://leetcode.com/problems/implement-trie-prefix-tree/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44struct Trie {
45        false
46    }
47
48
49/** 
50 * `&self` means the method takes an immutable reference.
51 * If you need a mutable reference, change it to `&mut self` instead.
52 */
53impl Trie {
54
55    fn new() -> Self {
56        
57    }
58    
59    fn insert(&self, word: String) {
60        
61    }
62    
63    fn search(&self, word: String) -> bool {
64        
65    }
66    
67    fn starts_with(&self, prefix: String) -> bool {
68        
69    }
70}
71
72/**
73 * Your Trie object will be instantiated and called as such:
74 * let obj = Trie::new();
75 * obj.insert(word);
76 * let ret_2: bool = obj.search(word);
77 * let ret_3: bool = obj.starts_with(prefix);
78 */
79
80// submission codes end
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    #[test]
87    fn test_208() {
88    }
89}
90