Даны две строки. Определите, можно ли получить одну из другой ровно одной
правкой: вставкой одного символа, удалением одного символа или заменой одного
символа на другой. (LeetCode 161 One Edit Distance.)
// IsOneEditDistance сообщает, отличаются ли s и t ровно на одну правку.
func IsOneEditDistance(s, t string) bool
Примеры
"ab", "acb" → true // вставка c
"cab", "ad" → false
"1203", "1213" → true // замена 0 → 1
"abc", "abc" → false // ноль правок — не «ровно одна»
"", "a" → true
Ограничения
0 ≤ len(s), len(t) ≤ 10⁶. Строки в UTF-8, символ — руна: "ёж" и "еж"
отличаются одной заменой.- Ожидается O(n) по времени. Таблица расстояния Левенштейна O(n·m) не пройдёт.
Устно: как проверить, что расстояние не больше k, быстрее, чем полной DP?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.