958. One Edit Away

A dictionary of n words is given, then q queries. For each query print yes if some dictionary word can be obtained from the query by EXACTLY ONE of these edits, and no otherwise:

· replace one character by a different one · delete one character · insert one character anywhere, including at either end

A dictionary word equal to the query is zero edits away and does not count.

``` dictionary cat cart act cart -> yes insert r into cat car -> yes replace t by r in cat catt -> yes delete a t and reach cat cat -> yes cart is one deletion from it

dictionary a b -> yes aa -> yes ab -> yes a -> no ```

## Why problem 957's walk is not enough

957 allows only replacement, so position k in the query always sits at depth k in the trie and the two move together. An insertion or a deletion breaks that alignment permanently: after the query has skipped a character, every later comparison is off by one.

Comparing the query against every dictionary word with an edit distance table costs n tables of 12 by 12, which at 20000 * 2000 queries is 5.76 * 10^9 cell updates.

## Four moves instead of one

Carry a node, a position k in the query and a budget. While the budget is unspent there are four things that can happen; once it is spent only the first remains.

``` search(node, k, used): if k == end of query: if used == 1: return isEnd[node] # budget unspent: the stored word may have one extra letter here return some child of node is an end of a word

c = query[k] if child[node][c] exists and search(child[node][c], k+1, used): return true if used == 0: for d in a .. z with child[node][d] present: if d != c and search(child[node][d], k+1, 1): return true # replace if search(child[node][d], k, 1): return true # word has an extra letter if search(node, k+1, 1): return true # word is missing this letter return false ```

Read the three spending moves as statements about the STORED word, not about the query. "Replace" moves both. "The word has an extra letter" moves the trie down and leaves k alone. "The word is missing this letter" moves k on and leaves the node alone.

## Why it terminates

The only move that does not advance k is the extra-letter move, and it can be taken only when used is 0 and it sets used to 1. So it happens at most once on any path, and every other move advances k by one towards the end of the query. There is no cycle to fall into.

## Why the budget rules give EXACTLY one edit

Every free step is a matching step, so a path that reaches the end with used == 1 differs from the stored word in precisely the one place where the budget was spent. A path with used == 0 at the end has matched the whole query against a complete stored word, which is zero edits, and the base case refuses it. The extra check in the base case covers the one edit that has no position inside the query: a letter appended past its end.

## The trailing insertion is the case everyone loses

a against the dictionary word aa needs a letter added AFTER the query is exhausted, and the main loop never runs there. Without the extra base-case check this answers no. It is the reason aa is in the second worked example.

## Against problem 624

624 is given two strings and asks whether they are AT MOST one edit apart, which two pointers settle in one pass. This searches a dictionary of up to 20000 words for a partner at EXACTLY one edit, and the trie is what stops the search from being 20000 separate comparisons.

## Cost

With used == 0 the reachable states are the at most 13 nodes on the query's own path. From each one, spending the budget opens at most 51 successors, and after that the walk is forced. So a query is a few thousand steps. Space is the trie, at most 1 + 20000 * 12 = 240001 nodes.

Constraints - `1 ≤ n ≤ 20000` - `1 ≤ q ≤ 2000` - Every dictionary word and every query is 1 to 12 lowercase English letters. - Dictionary words may repeat.