TheAlgorithms-Python

1
def edit_distance(source: str, target: str) -> int:
2
    """
3
    Edit distance algorithm is a string metric, i.e., it is a way of quantifying how
4
    dissimilar two strings are to one another. It is measured by counting the minimum
5
    number of operations required to transform one string into another.
6

7
    This implementation assumes that the cost of operations (insertion, deletion and
8
    substitution) is always 1
9

10
    Args:
11
    source: the initial string with respect to which we are calculating the edit
12
        distance for the target
13
    target: the target string, formed after performing n operations on the source string
14

15
    >>> edit_distance("GATTIC", "GALTIC")
16
    1
17
    """
18
    if len(source) == 0:
19
        return len(target)
20
    elif len(target) == 0:
21
        return len(source)
22

23
    delta = int(source[-1] != target[-1])  # Substitution
24
    return min(
25
        edit_distance(source[:-1], target[:-1]) + delta,
26
        edit_distance(source, target[:-1]) + 1,
27
        edit_distance(source[:-1], target) + 1,
28
    )
29

30

31
if __name__ == "__main__":
32
    print(edit_distance("ATCGCTG", "TAGCTAA"))  # Answer is 4
33