Question Link:

http://www.geeksforgeeks.org/check-if-two-given-strings-are-at-edit-distance-one/

An edit between two strings is one of the following changes:

  • Add a character
  • Delete a character
  • Change a character

Given two string s1 and s2, find if s1 can be converted to s2 with exactly one edit. Expected time complexity is O(m+n) where m and n are lengths of two strings.

Solution

There are three cases:

  1. Two strings have the same length, then check if there is only one character different.
  2. Two strings have 1 different on length, then check if one can be generated by adding 1 character to another.
  3. Otherwise, return False

Implementation

[-] Python code accepted by LeetCode OJ 


class Solution(object):
    def isEditDistanceOne(self, s1, s2):
        n = len(s1)
        m = len(s2)
        if n == m:
            return self.__isChangeOne(s1, s2, n)
        elif n == m - 1:
            return self.__isAddOne(s1, s2, n)
        elif n - 1 == m:
            return self.__isAddOne(s2, s1, m)
        else:
            return False

    def __isChangeOne(self, s1, s2, n):
        changed = False
        for i in range(n):
            if s1[i] != s2[i]:
                if changed:
                    return False
                changed = True
        return changed

    def __isAddOne(self, s1, s2, n):
        """
        Check if s2 can be generated by adding a character to s1
        :param s1: shorter string
        :param s2: longer string
        :param n: length of s1
        :return: boolean
        """
        add = 0
        for i in range(n):
            if s1[i] != s2[i + add]:
                if add == 1:
                    return False
                add = 1
        return add == 1

if __name__ == "__main__":
    sol = Solution()
    s1 = "gfg"
    s2 = "axag"
    print(sol.isEditDistanceOne(s1, s2))