noodleProblems/
Implement Trie (Prefix Tree)
#141

Implement Trie (Prefix Tree)

AlgorithmmediumTrieHash TableStringDesign

Design a **trie** (also called a *prefix tree*) — a structure that stores strings character by character so that lookups and prefix queries run in time proportional to the length of the key, not the number of keys stored.

The structure supports three operations:

- "insert" — add the word word to the trie. Returns null. - "search" — return true if the exact word was previously inserted, otherwise false. - "startsWith" — return true if any previously inserted word begins with prefix, otherwise false.

You are given the operations as two parallel arrays: operations[i] is the operation name and values[i] is its argument list ([word] for "insert"/"search", [prefix] for "startsWith"). Apply them in order and return an array holding each operation's return value (null for every "insert", a boolean for "search" and "startsWith").

For example ["insert","search","search","startsWith","insert","search"] with [["apple"],["apple"],["app"],["app"],["app"],["app"]] returns [null, true, false, true, null, true]. After inserting "apple": search("apple") is true; search("app") is false because "app" was never inserted as a complete word; startsWith("app") is true because "apple" begins with "app"; then "app" is inserted, so search("app") becomes true.

Example cases

  • insert, prefix vs full word
    in operations = ["insert","search","search","startsWith","insert","search"]values =
    apple
    apple
    app
    app
    app
    app
    out [null,true,false,true,null,true]
    search("app") is false until "app" is inserted as a full word, but startsWith("app") is true the moment "apple" exists.
  • misses on an empty / unmatched trie
    in operations = ["startsWith","insert","search","startsWith"]values =
    a
    dog
    do
    cat
    out [false,null,false,false]
    startsWith("a") is false on an empty trie; search("do") is false (only "dog" was inserted); startsWith("cat") is false (no word starts with it).

Constraints

  • 1 <= operations.length <= 3 * 10^4
  • operations[i] is one of "insert", "search", "startsWith".
  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist of lowercase English letters only.
Saved
operations =
["insert","search","search","startsWith","insert","search"]
values =
[["apple"],["apple"],["app"],["app"],["app"],["app"]]