A trie (say "try") is a tree that stores words so that you can look up whole words and word beginnings (prefixes) quickly. Tries are used in autocomplete and spell checkers, for example the suggestions you see while typing in a search box.
Build the class Trie:
Trie() creates an empty trie.void insert(String word) stores word in the trie.boolean search(String word) gives true only when exactly this word was stored before, otherwise false.boolean startsWith(String prefix) gives true when at least one stored word begins with prefix, otherwise false.
Examples
Example 1:
Input
["Trie","insert","insert","search","search","startsWith","startsWith"]
[[],["rail"],["rain"],["rain"],["rai"],["rai"],["ram"]]
Output
[null,null,null,true,false,true,false]
Explanation
Trie trie = new Trie();
trie.insert("rail");
trie.insert("rain");
trie.search("rain"); // true
trie.search("rai"); // false, "rai" was never added as a word
trie.startsWith("rai"); // true, "rail" and "rain" begin with "rai"
trie.startsWith("ram"); // false
Example 2:
Input
["Trie","search","insert","search","startsWith"]
[[],["go"],["go"],["go"],["g"]]
Output
[null,false,null,true,true]
Explanation
Trie trie = new Trie();
trie.search("go"); // false, the trie is empty
trie.insert("go");
trie.search("go"); // true
trie.startsWith("g"); // true