LeetCode 161: One Edit Distance

Problem Restatement

We are given two strings:

s
t

Return True if they are exactly one edit distance apart.

An edit means one of these operations:

The key word is exactly.

If the strings are already equal, the answer is False, because that needs zero edits.

LeetCode states the same definition: return true only when one insertion, deletion, or replacement can transform one string into the other. The constraints allow lengths from 0 to 10^4, and characters may be letters or digits.

Input and Output

Example function shape:

def isOneEditDistance(s: str, t: str) -> bool:
    ...

Examples

Example 1:

s = "ab"
t = "acb"

Insert "c" into s:

"ab" -> "acb"

So the answer is:

True

Example 2:

s = "cab"
t = "ad"

There is no way to get from "cab" to "ad" with exactly one edit.

So the answer is:

False

Example 3:

s = "1203"
t = "1213"

Replace "0" with "1":

"1203" -> "1213"

So the answer is:

True

Example 4:

s = ""
t = ""

The strings are already equal.

That is zero edits, so the answer is:

False

First Thought: Full Edit Distance

A general edit-distance solution uses dynamic programming.

It computes the minimum number of insertions, deletions, and replacements needed to transform one string into the other.

But this problem only asks whether the distance is exactly 1.

So full dynamic programming is unnecessary.

We can solve it with one scan.

Key Insight

If two strings are one edit apart, their lengths can differ by at most 1.

So first check:

abs(len(s) - len(t)) > 1

If true, return False.

Then compare the strings from left to right.

The first time characters differ, we decide which edit type must be used.

Algorithm

Let m = len(s) and n = len(t).

To simplify the logic, make sure s is the shorter string.

If s is longer than t, swap them.

Now there are only two cases.

Case 1: same length.

There must be exactly one replacement.

When we find the first mismatch at index i, the rest of the strings must be equal:

s[i + 1:] == t[i + 1:]

Case 2: t is longer by one character.

There must be exactly one insertion into s.

When we find the first mismatch at index i, skip one character in t, and the rest must match:

s[i:] == t[i + 1:]

If the loop finishes without finding a mismatch, then the only way to be one edit apart is for t to have exactly one extra character at the end.

So return:

n == m + 1

Walkthrough

Use:

s = "ab"
t = "acb"

Lengths are:

m = 2
n = 3

The strings differ by one length, so this could be an insertion.

Compare characters:

s[0] = "a"
t[0] = "a"

They match.

Next:

s[1] = "b"
t[1] = "c"

They differ.

Since t is longer, skip t[1].

Compare the rest:

s[1:] == t[2:]

That is:

"b" == "b"

So the answer is:

True

Correctness

If the length difference is greater than 1, one edit cannot make the strings equal. One insertion or deletion changes length by exactly 1, and one replacement does not change length. So returning False is correct.

After making s the shorter string, there are only two valid cases.

If the lengths are equal, the only possible one-edit operation is replacement. At the first mismatch, we must replace s[i] with t[i]. After that single edit, all remaining characters must already match. Therefore, the condition s[i + 1:] == t[i + 1:] is necessary and sufficient.

If t is longer by one character, the only possible operation is inserting one character into s. At the first mismatch, the inserted character must be t[i]. After skipping that character, the remaining suffixes must match. Therefore, the condition s[i:] == t[i + 1:] is necessary and sufficient.

If no mismatch is found during the scan, then one edit is possible only when the longer string has exactly one extra trailing character. That is exactly the condition n == m + 1.

So the algorithm returns True exactly when the strings are one edit distance apart.

Complexity

Let m = len(s) and n = len(t).

In Python, slicing creates new strings, so the slice version can allocate O(n) temporary space. The pointer version below avoids that.

Implementation

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        m = len(s)
        n = len(t)

        if m > n:
            return self.isOneEditDistance(t, s)

        if n - m > 1:
            return False

        for i in range(m):
            if s[i] != t[i]:
                if m == n:
                    return s[i + 1:] == t[i + 1:]

                return s[i:] == t[i + 1:]

        return n == m + 1

Code Explanation

We compute lengths first:

m = len(s)
n = len(t)

Then we make sure s is the shorter string:

if m > n:
    return self.isOneEditDistance(t, s)

This removes the need to separately handle deletion. Deleting from the longer string is equivalent to inserting into the shorter string.

If the length gap is too large:

if n - m > 1:
    return False

one edit cannot fix it.

Now scan both strings:

for i in range(m):

At the first mismatch:

if s[i] != t[i]:

If lengths are equal, we must use one replacement:

return s[i + 1:] == t[i + 1:]

If t is longer, we must use one insertion into s:

return s[i:] == t[i + 1:]

If no mismatch occurs, then the shorter string is a prefix of the longer one.

They are one edit apart only if the longer string has exactly one extra character:

return n == m + 1

Pointer Implementation Without Slicing

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        m = len(s)
        n = len(t)

        if abs(m - n) > 1:
            return False

        i = 0
        j = 0
        edits = 0

        while i < m and j < n:
            if s[i] == t[j]:
                i += 1
                j += 1
                continue

            edits += 1

            if edits > 1:
                return False

            if m == n:
                i += 1
                j += 1
            elif m < n:
                j += 1
            else:
                i += 1

        if i < m or j < n:
            edits += 1

        return edits == 1

This version counts mismatches directly and avoids creating suffix strings.

Testing

def run_tests():
    sol = Solution()

    assert sol.isOneEditDistance("ab", "acb") is True
    assert sol.isOneEditDistance("cab", "ad") is False
    assert sol.isOneEditDistance("1203", "1213") is True
    assert sol.isOneEditDistance("", "") is False
    assert sol.isOneEditDistance("a", "") is True
    assert sol.isOneEditDistance("", "A") is True
    assert sol.isOneEditDistance("abc", "abc") is False
    assert sol.isOneEditDistance("abc", "ab") is True
    assert sol.isOneEditDistance("abc", "adc") is True
    assert sol.isOneEditDistance("abc", "axc") is True
    assert sol.isOneEditDistance("abc", "abde") is False

    print("all tests passed")

run_tests()