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