Ежедневная часть (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.