A crossword setter keeps a dictionary words. For each string in queries, count the distinct
dictionary words that can be turned into the query with at most one edit, where an edit is
inserting one letter, deleting one letter, or replacing one letter with a different one. A query
that is itself in the dictionary counts that word too (zero edits).
Return a list with one count per query, in order. Repeated dictionary words count once.
Examples
Input: words = ["cart", "care", "car", "cat", "scar", "cars"], queries = ["car", "cxr", "cs"]
Output: [6, 1, 0]
Explanation: "car" itself, then "cart", "care", "cars" and "scar" (one insertion each) and
"cat" (one replacement). "cxr" only reaches "car". "cs" is two edits from every word.
Input: words = ["aa", "a", "aa", "b"], queries = ["", "a", "ab"]
Output: [2, 3, 3]
Explanation: "" is one insertion from "a" and "b". "a" reaches "a", "aa", "b".
"ab" reaches "aa", "a" and "b".
Constraints
0 <= len(words) <= 2 * 10**4,0 <= len(queries) <= 2000- Words and queries have length
0 .. 12and use lowercase letters (the empty word is allowed) - Target: much faster than comparing every query with every dictionary word
Goals
- Search a trie while spending at most one insertion, deletion or substitution
- Follow the rest of the query exactly once the edit is used
- Count each dictionary word once even when several edits reach it