LeetCode #208 Implement Trie (Prefix Tree)

Medium

Problem

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

It’s trivial to implement insert and startsWith methods. For search method, we use a boolean property to indicate if a node represents a word.

Complexity

Time complexity of all insert, search and startsWith operations are O(m) if m denotes to the given string because we have to go through entire string once.