JuniorКодЧастоЕщё не отвечали
Проверка строк на расстояние в одно редактирование
Верните true, если строку a можно превратить в строку b не более чем одним редактированием: одна вставка, одно удаление или одна замена символа.
Требования:
расстояния.
- O(n) время, O(1) дополнительной памяти — без матрицы редакционного
bool oneEditApart(const std::string& a, const std::string& b) {
// ваш код здесь
}Допишите реализацию.
Если длины различаются больше чем на 1, верните false. Если равны, посчитайте несовпадения символов и допустите не более одного. Если различаются на 1, идите двумя указателями, разрешив ровно один пропуск в длинной строке; любое второе несовпадение — отказ. Один проход, O(n) время, O(1) память.
- ✗Обрабатывать случаи равной длины и разницы в один одинаково, ошибаясь с пропуском при вставке/удалении
- ✗Забывать сразу отвергнуть, когда длины различаются больше чем на один
- ✗Допускать второе несовпадение после единственного разрешённого редактирования
- →Почему разница длин больше одного позволяет вернуть результат сразу?
- →Как пропуск двух указателей моделирует вставку против удаления?
Оглавление
Задача
Верните true, если из a получается b не более чем одним редактированием, за O(n) и O(1) памяти.
Решение
#include <string>
#include <cstdlib>
bool oneEditApart(const std::string& a, const std::string& b) {
int la = a.size(), lb = b.size();
if (std::abs(la - lb) > 1) return false;
if (la == lb) { // случай замены
int diff = 0;
for (int i = 0; i < la; ++i) if (a[i] != b[i] && ++diff > 1) return false;
return true;
}
const std::string& s = la < lb ? a : b; // короткая
const std::string& l = la < lb ? b : a; // длинная
int i = 0, j = 0; bool skipped = false;
while (i < static_cast<int>(s.size())) {
if (s[i] != l[j]) {
if (skipped) return false; // второй пропуск запрещён
skipped = true; ++j; // пропускаем в длинной
} else { ++i; ++j; }
}
return true;
}Ключевые моменты
- Разница длин > 1 — мгновенный отказ.
- Равные длины — это замена (считаем несовпадения, допускаем одно).
- Разница в 1 — вставка/удаление: один пропуск в длинной строке, второй запрещён.
Оглавление
