edit distance algorithm is a string metric i e it is a way of quantifying how dissimilar two strings are to one another it is measured by counting the minimum number of operations required to transform one string into another this implementation assumes that the cost of operations insertion deletion and substitution is always 1 args source the initial string with respect to which we are calculating the edit distance for the target target the target string formed after performing n operations on the source string editdistancegattic galtic 1 edit distance algorithm is a string metric i e it is a way of quantifying how dissimilar two strings are to one another it is measured by counting the minimum number of operations required to transform one string into another this implementation assumes that the cost of operations insertion deletion and substitution is always 1 args source the initial string with respect to which we are calculating the edit distance for the target target the target string formed after performing n operations on the source string edit_distance gattic galtic 1 substitution answer is 4
def edit_distance(source: str, target: str) -> int:
    
    if len(source) == 0:
        return len(target)
    elif len(target) == 0:
        return len(source)

    delta = int(source[-1] != target[-1])  
    return min(
        edit_distance(source[:-1], target[:-1]) + delta,
        edit_distance(source, target[:-1]) + 1,
        edit_distance(source[:-1], target) + 1,
    )


if __name__ == "__main__":
    print(edit_distance("ATCGCTG", "TAGCTAA"))