Build a trie (prefix tree) and drive it through a script of operations. You are given parallel arrays ops and words. For each i, ops[i] is one of "insert", "search" (exact word) or "startsWith" (any stored word begins with words[i]). Inserts produce no output; for each query append 'T' or 'F' to the answer. Return the answer string ("" if there were no queries).
Examples
Example 1:
Input: ops = ["insert","search","search","startsWith","insert","search"], words = ["apple","apple","app","app","app","app"]
Output: "TFTT"
Explanation: apple is found; app is not a stored word yet, but is a stored prefix; after inserting app it is found.
Example 2:
Input: ops = ["search"], words = ["a"]
Output: "F"
Example 3:
Input: ops = ["insert","startsWith","search"], words = ["ab","a","a"]
Output: "TF"
Constraints
1 <= ops.length = words.length <= 10^4
1 <= words[i].length <= 50, lowercase English letters
ops[i] is "insert", "search" or "startsWith"
Prerequisites
Tries — a tree keyed by character, where shared prefixes are shared nodes.
How to think about it
1. A Node Per Letter Optimal
Intuition
A trie stores words by their letters: each node holds a child per next character, and a flag saying "a word ends here". That flag is the only difference between search and startsWith — both walk the same path, and only search demands the flag at the end.
Algorithm
1. Insert: walk the word, creating missing children, then mark the last node as a word end. 2. Search: walk the word; succeed only if the path exists AND the last node is marked. 3. startsWith: walk the prefix; succeed if the path exists at all.
Time & Space
Time O(len) per operation. Space O(total letters inserted) — shared prefixes are stored once, which is the trie's whole economy over a set of strings.