0x91 - Distancia de Levenshtein

Si alguna vez has usado el programa Git y te has equivocado al escribir un comando, has visto que Git te da sugerencias de comandos similares que sí existen. Por ejemplo, aquí escribí comfit en vez de commit:

¿Pero alguna vez te has preguntado cómo está implementado?

Una posible solución es usar la distancia de Levenshtein, un concepto que fue propuesto en 1965 por el matemático ruso Vladimir Levenshtein y que nos permite medir qué tan similares o diferentes son dos strings. Más precisamente, la distancia de Levenshtein está definida de la siguiente manera:

Tenemos una string A y una string B. La distancia de Levenshtein entre A y B es el mínimo número de operaciones para transformar A en B, donde cada operación consiste en alguna de estas 3 alternativas:

• Insertar cualquier caracter en cualquier posición de A;
• Borrar cualquier caracter de A;
• Reemplazar un caracter A por cualquier otro caracter (sin cambiarlo de posición).

Veamos un ejemplo. Supongamos que tenemos la string inicial caos y queremos transformarla en codeo. Aquí hay una manera de transformarla:

En este caso usamos 4 operaciones, que de hecho es la mejor manera de hacerlo pues no es posible transformar caos en codeo usando 3 o menos operaciones (sin embargo, no es la única manera de hacerlo con 4 operaciones: otra manera de hacerlo es caos → caoso → caoeo → cadeo → codeo).

Dadas dos strings A y B, encuentra el mínimo número de operaciones para transformar una en la otra.

Entrada

La entrada contiene exactamente dos líneas:

• La primera línea contiene la string A;
• La segunda línea contiene la string B.

Ambas strings tienen entre 1 y 1000 caracteres y sólo tienen letras mínusculas. No hay eñes, tildes, o diéresis.

Salida

La salida debe tener una sóla línea con un número, la distancia de Levenshtein entre las dos strings.

Entrada de ejemplo 1

caos
codeo

Salida de ejemplo 1

4

Explicación del ejemplo 1

Este es el ejemplo explicado más arriba. La distancia es 4.

Entrada de ejemplo 2

codeo
codeo

Salida de ejemplo 2

0

Explicación del ejemplo 2

Si las dos strings son iguales, no necesitamos hacer ninguna operación para transformar una en la otra, por la tanto su distancia es 0.

Entrada de ejemplo 3

codeos
codeo

Salida de ejemplo 3

1

Explicación del ejemplo 3

Simplemente borramos la s.

Entrada de ejemplo 4

codo
codeo

Salida de ejemplo 4

1

Explicación del ejemplo 4

Simplemente insertamos la e que falta.

Entrada de ejemplo 5

codao
codeo

Salida de ejemplo 5

1

Explicación del ejemplo 5

Simplemente reemplazamos la a por e. Otra opción sería borrar la a y luego insertar la e (codao → codo → codeo) pero eso sería peor porque gastaríamos 2 operaciones en vez de 1.

Entrada de ejemplo 6

ab
ba

Salida de ejemplo 6

2

Explicación del ejemplo 6

Reemplazamos la a por la b y la b por la a usando 2 operaciones: ab → bb → ba.

Entrada de ejemplo 7

interesante
inteligente

Salida de ejemplo 7

4

Explicación del ejemplo 7

Sólo necesitamos 4 reemplazos en el medio para convertir resa en lige.

Entrada de ejemplo 8

interdisciplinariedad
contradictoriamente

Salida de ejemplo 8

14

Explicación del ejemplo 8

Buena suerte descifrando este.

Envía tu solución