One Edit Distance
Understanding the Problem
This problem is related to the general Edit Distance problem (LeetCode #72), but with one simplification: we only need to check whether the edit distance is exactly one, not compute its actual value. That removes the need for dynamic programming.
There are only three one-edit scenarios. If the two strings have the same length, the only valid edit is a replacement, so exactly one character must differ. If the lengths differ by one, the only valid edit is an insertion or deletion (the same operation viewed from either string). If the lengths differ by more than one, no single edit can bridge the gap.
Comparing the two lengths tells us which case applies, and a single pass verifies the edit. One subtlety to keep in mind: two equal strings are zero edits apart, so identical inputs must return false.
Key Constraints:
0 <= s.length, t.length <= 10^4→ Full edit-distance dynamic programming is O(m*n), which builds a table of up to 10^8 cells. Because we only need to confirm a single edit, an O(n) length-based check avoids that table entirely.- Strings can be empty → An empty string and a single character are one edit apart, but two empty strings are zero edits apart and return
false.
Approach 1: Edit Distance DP
Intuition
One way to solve this is to compute the full edit distance between s and t using dynamic programming, then check whether the result equals 1. This is the Levenshtein distance algorithm.
Build a 2D table where dp[i][j] is the minimum number of edits to convert the first i characters of s into the first j characters of t. Each cell depends on the three cells above, left, and diagonal, so we fill the table row by row and the answer ends up at dp[m][n].
This computes the entire edit distance when we only need to know whether it equals 1, which is more work than the problem requires.
Algorithm
- Let
m = len(s)andn = len(t). - Create a DP table of size
(m+1) x (n+1). - Initialize the first row and column:
dp[i][0] = ianddp[0][j] = j. - Fill the table: if
s[i-1] == t[j-1], thendp[i][j] = dp[i-1][j-1]. Otherwise,dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). - Return
dp[m][n] == 1.
Visualization and Code
Loading animation...
- Time Complexity: O(m * n). We fill an (m+1) x (n+1) DP table, doing O(1) work per cell.
- Space Complexity: O(m * n). The DP table requires (m+1) x (n+1) space.
The next approach drops the table. Because there are only three cases based on the length difference, each can be verified directly in a single pass.
Approach 2: One-Pass Length-Based Check (Optimal)
Intuition
If the edit distance between two strings is exactly one, the length difference alone narrows it to one of three cases:
- Same length: Exactly one position differs (a replacement).
- Lengths differ by 1: Removing one character from the longer string produces the shorter string (an insertion or deletion).
- Lengths differ by 2 or more: No single edit can bridge them, so return
falseimmediately.
The algorithm checks the length difference to pick the case, then verifies it with one scan.
To keep the code to two branches, ensure s is the shorter or equal-length string by swapping when s is longer. That leaves only len(s) == len(t) (replace) and len(t) - len(s) == 1 (insert into s / delete from t).
Stopping at the first mismatch is safe because a single edit can only fix one divergence. Up to position i the two strings are identical, so the one allowed edit must be spent at i. In the replace case the edit consumes the mismatched pair, and s[i+1:] == t[i+1:] confirms no second divergence exists. In the insert/delete case the edit consumes the extra character in t, so the remaining check shifts t by one: s[i:] == t[i+1:]. If either comparison fails, a second edit would be required, so the answer is false.
The sLen != tLen check at the end covers the case where every character of s matches the prefix of t and the only difference is one extra character at the end of t (for example s = "ab", t = "abc"). The loop never finds a mismatch there, so the final return distinguishes that valid one-edit case from identical strings.
Algorithm
- If the length difference is greater than 1, return
false. - Ensure
sis the shorter or equal-length string (swap if needed). - Scan both strings simultaneously to find the first mismatch.
- If lengths are equal (replace case): check that the rest of the strings after the mismatch are identical.
- If lengths differ by 1 (insert/delete case): skip the mismatched character in the longer string
t, then check that the rest matches. - If no mismatch is found during the scan, return
trueonly if the lengths differ by 1 (meaning the extra character is at the end oft).
Visualization and Code
Loading animation...
- Time Complexity: O(n). We scan through the shorter string once. The substring comparison after finding a mismatch is at most O(n) in total.
- Space Complexity: O(n). The substring operations create new strings of up to length n. This could be reduced to O(1) by comparing character-by-character instead of using substrings.