LeetCode 161: One Edit Distance Solution in Python Explained

Problem Statement

In LeetCode 161, you’re given two strings s and t. Your task is to determine if they are one edit away, where an edit is an insertion, deletion, or replacement of a single character, returning true if exactly one edit suffices, and false otherwise. The strings are not one edit away if they are identical. This differs from linked list intersection like LeetCode 160: Intersection of Two Linked Lists, focusing on string comparison rather than node convergence.

Constraints

• 0 <= s.length, t.length <= 10^4
• s and t consist of lowercase letters, uppercase letters, and digits

Example

Let’s see some cases:

Copy codeInput: s = "ab", t = "acb"
Output: true
Explanation: Insert 'c' between 'a' and 'b' in "ab" to get "acb".

Copy codeInput: s = "cat", t = "cut"
Output: true
Explanation: Replace 'a' with 'u' in "cat" to get "cut".

Copy codeInput: s = "cat", t = "cat"
Output: false
Explanation: Identical strings, no edit needed.

Copy codeInput: s = "cat", t = "dog"
Output: false
Explanation: Requires multiple edits.

These examples show we’re checking for a single edit difference.

Understanding the Problem

How do you solve LeetCode 161: One Edit Distance in Python? Take s = "ab", t = "acb". Inserting 'c' makes them match, so true. For "cat" and "cut", replacing 'a' with 'u' works, so true. If identical ("cat", "cat"), it’s false—no edit needed. For "cat" and "dog", multiple edits are required, so false. We need an efficient way to compare, not a substring task like LeetCode 159: Longest Substring with At Most Two Distinct Characters. We’ll use: 1. Two-Pointer Comparison: O(n) time, O(1) space—our best solution. 2. Recursive Edit Check: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Two-Pointer Comparison Approach

Explanation

Two-Pointer Comparison uses two pointers to traverse both strings, checking for a single edit:

• If lengths differ by more than 1, return false.
• Use pointers i and j for s and t.
• When characters differ:
• If lengths equal, skip both (replace).
• If s shorter, skip t (insert).
• If t shorter, skip s (delete).
• Ensure exactly one edit occurred.

This is the best solution due to its O(n) time complexity (n = max length), O(1) space usage (no extra structures), and straightforward logic, making it efficient and intuitive.

For "ab" and "acb":

• "a" matches, "b" vs "c" differs, skip t, "b" matches end, one edit (insert), true.

Step-by-Step Example

Example 1: s = "ab", t = "acb"

Goal: Return true.

• Start: i = 0, j = 0, edits = 0.
• Step 1: s[0]='a', t[0]='a', match, i=1, j=1.
• Step 2: s[1]='b', t[1]='c', differ, len(s)=2, len(t)=3.
• s shorter, j=2, edits=1.
• Step 3: s[1]='b', t[2]='b', match, i=2, j=3.
• Finish: edits=1, return true.

Example 2: s = "cat", t = "cut"

Goal: Return true.

• Start: i=0, j=0, edits=0.
• Step 1: c=c, i=1, j=1.
• Step 2: a!=u, lengths equal, i=2, j=2, edits=1.
• Step 3: t=t, i=3, j=3.
• Finish: edits=1, return true.

Example 3: s = "cat", t = "cat"

Goal: Return false.

• Start: i=0, j=0, edits=0.
• Steps: "c=c", "a=a", "t=t", all match.
• Finish: edits=0, return false.

How the Code Works (Two-Pointer Comparison) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef isOneEditDistance(s: str, t: str) -> bool:
    # Line 1: Check length difference
    if abs(len(s) - len(t)) > 1:
        # If lengths differ by > 1 (e.g., "ab" vs "abcd")
        return False

    # Line 2: Ensure s is shorter or equal for simplicity
    if len(s) > len(t):
        # Swap if s longer (e.g., "cat" vs "ca")
        return isOneEditDistance(t, s)

    # Line 3: Initialize pointers and edit count
    i = 0
    # Pointer for s (e.g., 0)
    j = 0
    # Pointer for t (e.g., 0)
    edits = 0
    # Edit count (e.g., 0)

    # Line 4: Compare strings
    while i < len(s) and j < len(t):
        # Traverse both (e.g., "ab" vs "acb")
        if s[i] != t[j]:
            # If chars differ (e.g., 'b' vs 'c')
            edits += 1
            # Increment edits (e.g., 1)
            if edits > 1:
                # More than one edit (e.g., "cat" vs "dog")
                return False
            if len(s) == len(t):
                # Replace case (e.g., "cat" vs "cut")
                i += 1
                j += 1
            else:
                # Insert case (e.g., "ab" vs "acb")
                j += 1
        else:
            # Chars match (e.g., 'a' vs 'a')
            i += 1
            j += 1

    # Line 5: Check remaining length difference
    if i == len(s) and j < len(t):
        # t has extra char (e.g., "ab" vs "abc")
        edits += 1

    # Line 6: Return result
    return edits == 1
    # True if exactly one edit (e.g., 1 for "ab" vs "acb")

This detailed breakdown clarifies how two-pointer comparison efficiently checks for one edit distance.

Alternative: Recursive Edit Check Approach

Explanation

Recursive Edit Check uses recursion to explore edit possibilities:

• Base case: If strings empty or differ by one char.
• Recurse: Check insert, delete, replace by skipping characters.
• Ensure exactly one edit.

It’s a practical alternative, O(n) time with O(n) space (recursion stack), but less efficient due to overhead and space usage.

For "ab" vs "acb":

• "ab" vs "acb" → skip 'c', "ab" vs "ab", one edit.

Step-by-Step Example (Alternative)

For "cat" vs "cut":

• Step 1: c=c, recurse on "at" vs "ut".
• Step 2: a!=u, try replace, "t" vs "t", one edit.
• Finish: Return true.

How the Code Works (Recursive)

Copy codedef isOneEditDistanceRecursive(s: str, t: str) -> bool:
    if s == t:
        return False
    if abs(len(s) - len(t)) > 1:
        return False

    def check(s: str, t: str, edits: int) -> bool:
        if edits > 1:
            return False
        if not s and not t:
            return edits == 1
        if not s:
            return len(t) == 1 and edits == 0
        if not t:
            return len(s) == 1 and edits == 0
        if s[0] == t[0]:
            return check(s[1:], t[1:], edits)
        return (check(s[1:], t[1:], edits + 1) or  # replace
                check(s, t[1:], edits + 1) or      # insert
                check(s[1:], t, edits + 1))        # delete

    return check(s, t, 0)

Complexity

• Two-Pointer Comparison:
• Time: O(n) – single pass.
• Space: O(1) – constant space.
• Recursive Edit Check:
• Time: O(n) – recursive calls.
• Space: O(n) – recursion stack.

Efficiency Notes

Two-Pointer Comparison is the best solution with O(n) time and O(1) space, offering efficiency and simplicity—Recursive Edit Check matches time complexity but uses O(n) space due to recursion, making it insightful but less optimal.

Key Insights

• Two-Pointer: Direct comparison.
• Recursion: Explores edit paths.
• One Edit: Exact difference.

Additional Example

For s = "abc", t = "ab":

• Goal: true.
• Two-Pointer: Delete 'c', one edit.

Edge Cases

• Empty: "", "a" → true.
• Identical: "ab", "ab" → false.
• Multiple Edits: "ab", "cd" → false.

Both solutions handle these well.

Final Thoughts

LeetCode 161: One Edit Distance in Python is a clever string comparison challenge. The Two-Pointer Comparison solution excels with its efficiency and clarity, while Recursive Edit Check offers a recursive perspective. Want more? Try LeetCode 72: Edit Distance for full edit distance or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 161 on LeetCode with "ab" and "acb", aiming for true—test your skills now!