161 One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

One edit distance means that two strings will be identical by either one update, delete, or add operation.

The Idea: This is the type of problem that is fairly simple, but can easily get messy. I've added comments below in the code explains all cases that can happen.

Complexity: O(n) time and O(1) space

class Solution(object):
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """

        s_larger = len(s) >= len(t)
        t_larger = len(s) <= len(t)
        for i in range(min(len(s), len(t))):
            if s[i] != t[i]:
                # cases:
                # 1. if both are the same length, then both
                # s and t need to be incremented and be the same

                # 2. if s is larger and t is smaller then
                # s can move one iterator to match the length of t
                # and t must remain the same length

                # 3. if t is larger and s is smaller, then
                # the reverse must be true
                return s[i + s_larger:] == t[i + t_larger:]

        # if the lengths are the same return False
        return abs(len(s) - len(t)) == 1


obj = Solution()
print(obj.isOneEditDistance('ab', 'ba'))  # False
print(obj.isOneEditDistance('abc', 'ab'))  # True
print(obj.isOneEditDistance('ab', 'cab'))  # True
print(obj.isOneEditDistance('a', ''))  # True
print(obj.isOneEditDistance('abb', 'abc'))  # True
print(obj.isOneEditDistance('a', 'a'))  # False
print(obj.isOneEditDistance('acc', 'adc'))  # True
print(obj.isOneEditDistance('kkk', 'kkc'))  # True
print(obj.isOneEditDistance('lmk', 'kml'))  # False
print(obj.isOneEditDistance('abcde', 'abfde'))  # True
print(obj.isOneEditDistance('abcde', 'abffe'))  # False

Last updated