28. Diferencia entre textos

Crea una función que calcule la "distancia de edición" (también conocida como distancia de Levenshtein) entre dos cadenas de texto. Esta distancia representa el número mínimo de ediciones de un solo carácter (inserciones, eliminaciones o sustituciones) necesarias para transformar una cadena en la otra.

La función debe aceptar dos cadenas de texto (cadena1, cadena2) y devolver un número entero que represente la distancia de Levenshtein.

def distancia_levenshtein(cadena1: str, cadena2: str) -> int:
    # Tu código aquí
    pass

distancia_levenshtein("kitten", "sitting")
# 3 (k -> s, e -> i, _ -> g)

distancia_levenshtein("flaw", "lawn")
# 2

distancia_levenshtein("saturday", "sunday")
# 3

distancia_levenshtein("", "abc")
# 3

distancia_levenshtein("abc", "")
# 3

distancia_levenshtein("abc", "abc")
# 0

Ratoncito

Implementa el algoritmo de Levenshtein utilizando recursión o una tabla de programación dinámica (siempre que el uso de la tabla no sea una "variable modificable" en el sentido de las reglas del libro; es decir, que la tabla se construya inmutablemente o se pase recursivamente).

Dragón

Optimiza el uso de memoria si la implementación con tabla es demasiado intensiva para cadenas muy largas (por ejemplo, reduciendo la memoria utilizada a solo dos filas de la tabla). Explica las complejidades de tiempo y espacio del algoritmo.