Gegeben sind ein Start- und ein Zielwort und die Operationen, einen Buchstaben zu entfernen, in einen anderen umzuwandeln und einen neuen Buchstaben an einer beliebigen Stelle einzufügen. Du interessierst dich nun dafür, mit möglichst wenigen Operationen das Start- in das Zielwort umzuwandeln.
Du hast dir die folgende Strategie überlegt:
Man gehe das Zielwort Buchstabe für Buchstabe durch. Wenn am Startwort an diesem Index der falsche Buchstabe steht, so wandle ihn in den richtigen um. Ist das Startwort länger als das Zielwort, so entferne die hinteren Buchstaben. Ist es kürzer, so füge die entsprechenden Buchstaben am Ende ein.
Führt diese Strategie immer zu der optimalen Lösung?
