Как преобразовать одну строку в другую с минимальным количеством правок?

Question

Мне задавали этот вопрос во время телефонного интервью.

Учитывая две строки, найдите минимальное количество правок, необходимых для преобразования одной строки в другую. Решение должно быть реализовано в Java и работать в O (n * m), предполагая, что n и m являются длинами входных строк.

Пример:
строки: молоко -> пиво
Мин. правки: 4

Answer 1

Для строк различной длины используйте Расстояние Левенштейна: http://en.wikipedia.org/wiki/Levenshtein_distance

Если у вас есть строки одинаковой длины и вы не хотите рассматривать вставки или удаления, расстояние Хемминга будет более эффективным: http://en.wikipedia.org/wiki/Hamming_distance

Пример реализации расстояния Левенштейна: http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance

Answer 2

Предположение: слово содержит разные буквы.

Как насчет создания Character Hashset для S1.

Теперь переберите каждый символ в S2 и попробуйте удалить его из Hashset из S1. Если вы можете удалить символ, не увеличивайте счетчик. еще увеличить счетчик.

Счетчик содержит минимальное количество правок.