Сделать из строки A строку B

[stuxjkee]

Какое наименьшее количество операций(добавить 1 символ, удалить 1 символ, заменить 1 символ) нужно сделать, чтобы из строки A получить строку B?

[Stilet]

Минимум одну операцию, при условии что удаляемый символ и заменяемый равны.

[Poma][a]

uses Math;

var
    a, b : string;
    s : array ['a'..'z'] of Integer;
    i, sum : Integer;
    ch : Char;

begin
    ReadLn(a);
    ReadLn(b);

    for ch := Low(s) to High(s) do s[ch] := 0;

    for i := 1 to Length(a) do
        Inc(s[a[i]]);

    for i := 1 to Length(b) do
        Dec(s[b[i]]);

    sum := 0;

    for ch := Low(s) to High(s) do
        Inc(sum, Abs(s[ch]));
    
    WriteLn(IfThen(Odd(sum), sum, sum div 2)) // к разговору о вчерашней теме, где я не успел отписаться :(
end.

P.S. Не проверял..

[Serge_Bliznykov]

имхо тут далеко не всё просто и очевидно.

Poma][a, подскажите, Ваша программа найдёт, например,
что из строки
колад -> оклад
нужно два изменения

а из строки
башмак -> шумок
нужно сделать 4 изменения?

[Аватар]

из строки A получить строку B

Если для общего случая, то max(N,M) где N и M количество символов в строках. Это для самого тяжелого случая - ни один символ из строки B не встречается в строке А

[Poma][a]

имхо тут далеко не всё просто и очевидно.

Ага..

Poma][a, подскажите, Ваша программа найдёт, например,
что из строки

1) Я коварно ввел ограничения на маленькие латинские буквы..
2) Понял.. Спасибо..

Всё печально.. И в основном из-за замена..

[Somebody]

Это называется расстояние Левенштейна.

[Serge_Bliznykov]

Сообщение от Somebody

Это называется расстояние Левенштейна.

Вот, именно! В голове крутилось, что я такую задачу где-то видел, и даже про расстояние вспомнил. Но только ваш пост всё окончательно прояснил!
спасибо.