Ежедневная часть (e) C++ # 23, Общие проблемы на собеседованиях: расстояние редактирования
Сегодня мы рассмотрим распространенную задачу интервью C++: вычисление расстояния редактирования между двумя строками.
Расстояние редактирования — это минимальное количество правок, необходимое для преобразования первой строки во вторую.
Разрешенные правки: добавить персонажа, удалить символ и заменить символ.
В этом примере расстояние редактирования равно 3 с двумя операциями замены и одним добавлением.
Прежде чем продолжить чтение решения, попробуйте решить его самостоятельно. Вот ссылка на проводник компилятора с парой тестов: https://compiler-explorer.com/z/v6cqM7T6M.
Решение
Тривиальный подход состоял бы в том, чтобы перебрать две строки, пробуя все три операции всякий раз, когда мы сталкиваемся с различием.
К сожалению, это быстро взрывается. Если бы две строки не пересекались, мы бы умножили количество состояний на 3 для каждого символа, что привело бы к временной сложности O(3^N)
.
Поэтому нам нужно что-то получше.
Как это обычно бывает с проблемами такого типа, стоит подумать, можем ли мы вычислить количество правок по количеству правок для более коротких строк, что позволит нам вычислить количество правок итеративно.
Рассмотрим три операции:
- кроме того, если мы знаем расстояние редактирования между
"abc"
и"xyz"
(назовем егоdist
), то расстояние редактирования между"abc"
и"xyzR"
равно простоdist+1
- для удаления, если мы знаем расстояние редактирования между
"abc"
и"xyz"
, то расстояние редактирования между"abcP"
и"xyz"
равно простоdist+1
- для замены, если мы знаем расстояние редактирования между
"abc"
и"xyz"
, то расстояние редактирования между"abcP"
и"xyzR"
равноdist+1
, еслиP!=R
, илиdist
, еслиP==R
Единственное, что нам еще нужно, это определить минимум правок. Для этого нам нужно рассмотреть все три операции и взять минимальное из этих чисел.
Поскольку мы делаем это итеративно, конечный результат гарантированно будет минимальным.
#include <string_view> #include <vector> #include <numeric> int editDistance(std::string_view word1, std::string_view word2) { std::vector<int> distance(word2.length() + 1); // Starting from an empty string, // we can reach any string by simply adding: std::iota(distance.begin(), distance.end(), 0); // i, j the prefix length for (size_t i = 1; i < word1.length() + 1; i++) { std::vector<int> next(word2.length() + 1); // If the target is an empty string, // the number of edits is simply the length of the prefix. next[0] = i; for (size_t j = 1; j < word2.length() + 1; j++) { // Minimum of add and remove next[j] = std::min(next[j - 1] + 1, distance[j] + 1); // Add replace based on whether the characters match: if (word2[j - 1] == word1[i - 1]) next[j] = std::min(next[j], distance[j - 1]); else next[j] = std::min(next[j], distance[j - 1] + 1); } distance = std::move(next); } return distance[word2.length()]; }
Откройте решение в Compiler Explorer.