MayChallege (44) | Implement Trie (Prefix Tree)

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

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

Me: Prefix Tree is  Data Structure simple and these is many usefuls  uses, example as Addon Auto Complete of Google search bar:

One more app as Spell Checker,  IpRouting, and Solving Word Game. In the past, i used to be scared must be implement Prefix Tree, because with me, it is too very understand. But now, i can implement it very quick. Because i would practive day-by-day many time.

Imagine Prefix Tree is a tree in each Node is array character from a -> z, if you implement with Map, you don't convert to int, else: index = character - 'a', so index = 0 -> 26.  If a character you stand have not in Prefix Tree, you will declare it. View image below you will understand:

If you implement Binary Tree, in each Node only 2 children is left and right, so imagine Prefix Tree will 26 chilren each node, good luck, and here code me:

Thanks you, see you later !