Задача: 72. Edit Distance
Сложность: medium

Даны два слова word1 и word2. Верните минимальное количество операций, необходимых для преобразования word1 в word2.
Доступны следующие три операции над словом:
Вставить символ.
Удалить символ.
Заменить символ.

Пример:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

👨‍💻 Алгоритм:

1️⃣Подход динамического программирования с верху вниз реализуется путем добавления кэширования в рекурсивные вызовы функций. Например, в рекурсивном вызове будут следующие параметры: word1 = abc, word2 = ad, word1Index = 2 (с индексацией от нуля) и word2Index = 1 (с индексацией от нуля).

2️⃣Для кэширования результата данной подзадачи необходимо использовать структуру данных, которая хранит результат для word1, заканчивающегося на индексе word1Index, то есть 2, и word2, заканчивающегося на word2Index, то есть 1. Один из возможных способов реализации - использование двумерного массива, например, memo, где memo[word1Index][word2Index] кэширует результат для word1, заканчивающегося на word1Index, и word2, заканчивающегося на word2Index.

3️⃣Индексы word1Index и word2Index указывают на текущие символы строк word1 и word2 соответственно. Алгоритм реализуется по следующей схеме: перед вычислением результата подзадачи проверяется, не сохранен ли он уже в memo[word1Index][word2Index]. Если да, то возвращается сохраненный результат. После вычисления результата каждой подзадачи результат сохраняется в memo для будущего использования.

😎 Решение:

var minDistance = function (word1, word2) {
    let memo = Array(word1.length + 1)
        .fill()
        .map(() => Array(word2.length + 1).fill(null));
    function minDistanceRecur(word1, word2, word1Index, word2Index) {
        if (word1Index === 0) {
            return word2Index;
        }
        if (word2Index === 0) {
            return word1Index;
        }
        if (memo[word1Index][word2Index] !== null) {
            return memo[word1Index][word2Index];
        }
        let minEditDistance = 0;
        if (word1[word1Index - 1] === word2[word2Index - 1]) {
            minEditDistance = minDistanceRecur(
                word1,
                word2,
                word1Index - 1,
                word2Index - 1,
            );
        } else {
            let insertOperation = minDistanceRecur(
                word1,
                word2,
                word1Index,
                word2Index - 1,
            );
            let deleteOperation = minDistanceRecur(
                word1,
                word2,
                word1Index - 1,
                word2Index,
            );
            let replaceOperation = minDistanceRecur(
                word1,
                word2,
                word1Index - 1,
                word2Index - 1,
            );
            minEditDistance =
                Math.min(
                    insertOperation,
                    Math.min(deleteOperation, replaceOperation),
                ) + 1;
        }
        memo[word1Index][word2Index] = minEditDistance;
        return minEditDistance;
    }
    return minDistanceRecur(word1, word2, word1.length, word2.length);
};

Ставь 👍 и забирай 📚 Базу знаний