Расстояние редактирования
Hard
Даны две строки
Это расстояние редактирования (Левенштейна). Если строки уже равны, ответ 0; если одна пуста — ответ равен длине другой.
word1 и word2. Найдите минимальное число операций, чтобы превратить word1 в word2. Разрешены операции над одним символом: вставка, удаление и замена.Это расстояние редактирования (Левенштейна). Если строки уже равны, ответ 0; если одна пуста — ответ равен длине другой.
Примеры:
Вход:
{"word1": "horse", "word2": "ros"}
Выход:
3
Объяснение: horse → ros: один из кратчайших путей длины 3, например horse → rorse (замена h→r) → rose (удаление r) → ros (удаление e).
Вход:
{"word1": "intention", "word2": "execution"}
Выход:
5
Объяснение: intention → execution: минимально нужно 5 операций.
Вход:
{"word1": "", "word2": ""}
Выход:
0
Объяснение: Обе строки пустые: уже совпадают → 0 операций.
Ограничения:
0 <= word.length <= 500
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!