Implement Trie (Prefix Tree) — Medium Coding Interview Question

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

Example

Input: insert("apple"), search("apple") -> true, search("app") -> false, startsWith("app") -> true

Output: true

Constraints

• 1 <= word.length <= 2000

Topics & Companies

Topics: trie

Asked by: Google, Amazon

Optimal Solution Complexity

Time complexity: O(L). Space complexity: O(N * L).

Practice more

• All DSA Problems
• DSA Patterns