Build a word store that can search with wildcards, driven by a script. You are given parallel arrays ops and words. "add" stores words[i]; "search" asks whether any stored word matches words[i], where '.' in the query matches exactly one arbitrary letter. Append 'T' or 'F' per search and return the answer string.
Examples
Example 1:
Input: ops = ["add","add","add","search","search","search","search"], words = ["bad","dad","mad","pad","bad",".ad","b.."]
Output: "FTTT"
Example 2:
Input: ops = ["add","search","search"], words = ["a",".","a"]
Output: "TT"
Example 3:
Input: ops = ["add","add","search","search"], words = ["at","and","a.","an."]
Output: "TT"
Constraints
1 <= ops.length = words.length <= 10^4
1 <= words[i].length <= 25
Added words are lowercase letters; queries may also contain '.'
Prerequisites
Tries — a tree keyed by character, where shared prefixes are shared nodes.
How to think about it
1. Trie Walk That Branches on a Dot Optimal
Intuition
Adding is an ordinary trie insert; searching is where the wildcard changes the shape. A concrete letter follows exactly one child, but a dot has to try every child at that depth — so search becomes a DFS over the trie rather than a walk down it. That branching is why this is the trie problem interviewers prefer to plain lookup.
Algorithm
1. Add: ordinary trie insert. 2. Search: recurse with the node and the position in the query. 3. At the end of the query, succeed only if the node marks a word. 4. A letter descends its one child; a dot tries them all.
Time & Space
Time O(len) for a query with no dots; worst case O(26^dots x len). Space O(total letters).