"""
Check if edit distance between two strings is 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.
"""


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))