Расстояние Левенштейна между строками, состоящими из символов английского алфавита, вычисляется как минимальная суммарная стоимость последовательности действий, позволяющих преобразовать одну строку в другую. Разрешенные действия:
- замена: стоимость замены одного символа на другой равна разности порядковых номеров этих символов в алфавите.
- вставка/удаление: стоимость вставки символа в строку или удаления символа из строки равна порядковому номеру этого символа в алфавите (см. примеры).
Вам даны две строки. Найдите расстояние Левенштейна между ними.
Выходные данные
Выведите одно число — расстояние Левенштейна между этими строками.
Примечание
В первом примере следует заменить a на b (стоимость 1), r на u (стоимость 3) и c на g (стоимость 4).
Во втором примере следует вставить r (стоимость 18) и заменить m на n (стоимость 1).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
arc
bug
|
8
|
|
2
|
dome
drone
|
19
|