Tries Prefix trees

422. Implement Trie (Prefix Tree)

A trie, or prefix tree, stores a set of words so that it can quickly answer two questions: is this word in the set, and does any word in the set start with these letters? Write a class Trie with three methods:

insert(word) adds word to the set. Adding a word that is already there changes nothing.
search(word) returns true if word was added, and false otherwise.
startsWith(prefix) returns true if some added word starts with prefix, and false otherwise.

A word starts with itself, so startsWith("tree") is true once "tree" is added. Each method must run in O(L) time, where L is the length of its argument, however many words the trie holds.

Your class is tested by replaying a list of calls on a new, empty Trie. ops[i] names the i-th call: "insert", "search" or "startsWith", and words[i] is the word or prefix it is called with. The answer is the list of every value that search and startsWith return, in the order they are called.

In C# and Go the methods are Insert, Search and StartsWith, and in Rust startsWith is starts_with. Go creates the trie with Constructor(), and Rust with Trie::new(). The names in ops are the same in every language.

Example 1

Input: ops = ["insert", "insert", "search", "startsWith", "search", "startsWith"] words = ["tree", "trie", "tri", "tri", "trie", "trees"]

Output: [false,true,true,false]

Explanation: "tri" was never added, so search("tri") is false, but both added words start with it. "trie" was added. No added word starts with "trees", which is longer than "tree".

Example 2

Input: ops = ["insert", "search", "startsWith", "search", "insert", "search"] words = ["a", "a", "a", "ab", "ab", "ab"]

Output: [true,true,false,true]

Explanation: "a" is a word and also a prefix of itself. "ab" is not in the set until the second insert.

Example 3

Input: ops = ["search", "startsWith", "insert", "insert", "search", "startsWith"] words = ["x", "x", "xyz", "xyz", "xyz", "xyzz"]

Output: [false,false,true,false]

Explanation: Nothing has been added when the first two calls run, so both are false. Adding "xyz" twice keeps one copy.

Check your understanding

Work out the answer for this input before you write any code.

ops = ["insert", "search", "startsWith", "search"] words = ["car", "ca", "ca", "car"]

Constraints

1 ≤ ops.length ≤ 10⁵
Each ops[i] is "insert", "search" or "startsWith".
words.length equals ops.length.
1 ≤ words[i].length ≤ 100
The words in words have at most 10⁶ letters in all.
Each words[i] is made of lowercase English letters.

Clarifying questions

What you would ask an interviewer before writing any code.