Monday, April 1, 2019

Leetcode solution 208: Implement Trie (Prefix Tree)

Problem Statement 

Implement a trie with insertsearch, and startsWith methods.
Trie trie = new Trie();

trie.insert("apple");"apple");   // returns true"app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");"app");     // returns true
  • 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:

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



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)


No comments:

Post a Comment

Thank your for your comment! Check out us at if you need mock interviews!