624. One Edit Apart
Two strings are given. Print Yes if one can be turned into the other using AT MOST ONE
edit, and No otherwise. An edit is one of:
· replace a single character · insert a single character · delete a single character
Since it is "at most one", two equal strings answer Yes.
cat cut -> Yes replace a
ab acb -> Yes insert c
cat cat -> Yes no edit needed
cat dog -> No three replacements
## Why the edit distance table is the wrong tool
Problem 506 computes the full edit distance with an O(n * m) table. It answers this question
too, and it is far more machinery than a yes-or-no about ONE edit needs.
When the answer only has to distinguish "0 or 1" from "2 or more", the table is replaced by a single scan, and the length difference alone settles most inputs before any character is compared.
## Start with the lengths
If the lengths differ by more than 1, no single edit can close the gap: a replacement changes
none, and an insertion or deletion changes exactly one. Answer No immediately.
That leaves two cases.
## Equal lengths: count the mismatches
Only a REPLACEMENT is possible, since inserting or deleting would change the length. Walk both
strings together and count positions where they differ; the answer is Yes when the count is
at most 1.
## Lengths differing by one: skip once
Only an INSERTION into the shorter, equivalently a deletion from the longer, is possible. Walk a pointer along each:
while i < short and j < long:
if short[i] == long[j]: i += 1; j += 1
else:
if already skipped: answer No
skipped = true
j += 1 advance the LONGER one only
Advancing only the longer pointer is the edit itself. Advancing both would be a replacement, which is not available when the lengths differ.
If the loop finishes, the answer is Yes: any characters left over in the longer string are
at most one, and that one is the skipped insertion.
## The input that separates the two cases
pale and ple answer Yes by skipping a. pale and bake answer No: the lengths are
equal, so only replacement is allowed, and two positions differ.
A solution that handles only equal lengths passes cat/cut and fails pale/ple; one that
handles only the skip case fails pale/bake. Both are in the tests.
## Cost
Time O(n + m). Space O(1).
Constraints - `1 ≤ length of each string ≤ 200000` - both strings contain only lowercase letters
Input
The first line contains the first string. The second line contains the second string.
Output
Print Yes or No on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.