Leetcode solution 208: Implement Trie (Prefix Tree)

Problem Statement 

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.

Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Trie (prefix tree) is a very common data structure that appears very often in interviews. I used to get asked Trie at Fitbit, Snap and Google back in the days. I highly recommend you brush up on this basic data structure.

Please refer to this Baozi Training Blog for a modified version explained:
https://blog.baozitraining.org/2019/03/leetcode-solution-211-add-and-search.html

Leetcode actually did a great job explaining this problem. Feel free to download the explanation here (all credit and copyright goes to leetcode, obviously) 

Solutions

 

Time Complexity: assuming N is the word length, insert O(N), search O(N), startWith O(N)
Space Complexity: assuming N is the word length, insert O(N), search O(1), startWith O(1)

References

• Leetcode official solution