Минимальное количество необходимых операций - PullRequest
1 голос
/ 01 декабря 2009

У меня проблема, предположим, у меня есть заданная строка: "best", целевой строкой является: "beast". Затем я должен определить количество операций для преобразования данной строки в целевую строку, однако допустимые операции: 1. добавить символ в строку. 2. удалить персонажа. 3. поменяйте местами две позиции (следует использовать с умом, у нас есть только один шанс поменяться.)

В приведенном выше случае это 1. Как мы решаем такую ​​проблему, и что это за проблема? Я начинающий ученик.

Ответы [ 2 ]

3 голосов
/ 01 декабря 2009

Одна из широко используемых мер такого рода называется расстоянием Левенштейна.

http://en.wikipedia.org/wiki/Levenshtein_distance

На странице WP также упоминаются / ссылки на другие подобные понятия. По сути это метрика количества правок, необходимых для превращения одного слова в другое.

1 голос
/ 01 декабря 2009
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...