this script is a implementation of the dameraulevenshtein distance algorithm it s an algorithm that measures the edit distance between two string sequences more information about this algorithm can be found in this wikipedia article https en wikipedia orgwikidameraue28093levenshteindistance implements the dameraulevenshtein distance algorithm that measures the edit distance between two strings parameters firststring the first string to compare secondstring the second string to compare returns distance the edit distance between the first and second strings dameraulevenshteindistancecat cut 1 dameraulevenshteindistancekitten sitting 3 dameraulevenshteindistancehello world 4 dameraulevenshteindistancebook back 2 dameraulevenshteindistancecontainer containment 3 dameraulevenshteindistancecontainer containment 3 create a dynamic programming matrix to store the distances initialize the matrix fill the matrix transposition implements the damerau levenshtein distance algorithm that measures the edit distance between two strings parameters first_string the first string to compare second_string the second string to compare returns distance the edit distance between the first and second strings damerau_levenshtein_distance cat cut 1 damerau_levenshtein_distance kitten sitting 3 damerau_levenshtein_distance hello world 4 damerau_levenshtein_distance book back 2 damerau_levenshtein_distance container containment 3 damerau_levenshtein_distance container containment 3 create a dynamic programming matrix to store the distances initialize the matrix fill the matrix deletion insertion substitution transposition
def damerau_levenshtein_distance(first_string: str, second_string: str) -> int:
    
    
    dp_matrix = [[0] * (len(second_string) + 1) for _ in range(len(first_string) + 1)]

    
    for i in range(len(first_string) + 1):
        dp_matrix[i][0] = i
    for j in range(len(second_string) + 1):
        dp_matrix[0][j] = j

    
    for i, first_char in enumerate(first_string, start=1):
        for j, second_char in enumerate(second_string, start=1):
            cost = int(first_char != second_char)

            dp_matrix[i][j] = min(
                dp_matrix[i - 1][j] + 1,  
                dp_matrix[i][j - 1] + 1,  
                dp_matrix[i - 1][j - 1] + cost,  
            )

            if (
                i > 1
                and j > 1
                and first_string[i - 1] == second_string[j - 2]
                and first_string[i - 2] == second_string[j - 1]
            ):
                
                dp_matrix[i][j] = min(dp_matrix[i][j], dp_matrix[i - 2][j - 2] + cost)

    return dp_matrix[-1][-1]


if __name__ == "__main__":
    import doctest

    doctest.testmod()