[Algo Rhythm🕺💃] LeetCode 208. Implement Trie (Prefix Tree)

📚 Problem description

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.

 

🎯 Solution

 

🧐 Approach

Trie is one of efficient data structure when dealing with string.

There are two different way to represent trie. One is using array, and the other is using hash map.

Using array is more efficient rather than hash map. However, for flexibility, I chose hash map.

 

📖  What I learned

I implemented trie from scratch!