161. One Edit Distance

Problem Statement

link: LeetCode.cn LeetCode Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

Insert exactly one character into s to get t. Delete exactly one character from s to get t. Replace exactly one character of s with a different character to get t.

Example:

Input: s = "ab", t = "acb" Output: true

Input: s = "", t = "" Output: false

Constraints: 0 <= s.length, t.length <= 104 s and t consist of lowercase letters, uppercase letters, and digits.

Solution Approach

The solution uses a two-pointer approach to compare the strings, handling cases of insertion, deletion, or replacement of one character to determine if they are exactly one edit distance apart.

Algorithm

1. Length Check:First, the solution compares the lengths of the strings s and t. If the length difference is more than 1, return False immediately, as they can’t be one edit distance apart.
2. Character Comparison:Iterate through the characters of both strings using a loop. If a mismatch is found, check whether replacing the character or deleting/inserting a character can make the strings identical from that point onward.
3. Final Check:After the loop, if no differences are found, the strings are one edit distance apart only if their lengths differ by exactly one character.

Implement

    class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)
        if m < n:
            return self.isOneEditDistance(t, s)
        if m - n > 1:
            return False
        foundDifference = False
        for i, (x, y) in enumerate(zip(s, t)):
            if x != y:
                foundDifference = True
                return s[i + 1:] == t[i + 1:] if m == n else s[i + 1:] == t[i:]
        return foundDifference or m - n == 1

    
    

Twitter  facebook  Email