One Edit Distance - Leetcode Solution

One Edit Distance problem on leetcode The problem can be found on the following link: https://leetcode.com/problems/one-edit-distance/

Problem Statement

Given two strings s and t, determine if they are both one edit distance apart.

Note:

There are three possibilities to consider: 1) s and t are of equal length and only one character has been changed; 2) s is one character shorter than t and adding one character to s makes it equal to t; 3) t is one character shorter than s and adding one character to t makes it equal to s.

Example 1:

Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t.

Example 2:

Input: s = "cab", t = "ad" Output: false Explanation: We cannot get t from s by only one step.

Example 3:

Input: s = "1203", t = "1213" Output: true Explanation: We can replace '0' with '1' to get t.

Solution

The solution to this problem involves comparing each character of the two strings. If the two strings are the same length, only one character can differ for them to be one edit distance apart. If they are of different length, then there must be one character added or deleted to one of the strings in order to make them equal.

step 1: We start by comparing the length of the two strings. If the absolute difference between their lengths is greater than 1, then it is impossible for them to be one edit distance apart and we return false.

step 2: Then, we iteratively compare each character of the two strings. If we find a character that does not match, we check if we have found a difference before. If we have, then we know that more than one edit distance is required, and we return false. If this is the first difference we have found, we mark it and continue comparing the rest of the characters.

step 3: If we have iterated through the entire strings without finding a second difference, then the strings are only one edit distance apart, and we return true.

Here is the code implementation of this logic:

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        ls, lt = len(s), len(t)
        if abs(ls-lt) > 1:     # Step 1
            return False
        
        if ls > lt:
            return self.isOneEditDistance(t, s)     # To ensure s is shorter than t
        
        for i in range(ls):
            if s[i] != t[i]:
                if ls == lt:
                    return s[i+1:] == t[i+1:]
                else:
                    return s[i:] == t[i+1:]
        
        return ls+1 == lt    # Step 3

This implementation has a time complexity of O(n), where n is the length of the shorter string. This is because we iterate through all the characters in the shorter string.

1