Задача: 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 для будущего использования.

😎 Решение:

class Solution {
    Integer memo[][];

    public int minDistance(String word1, String word2) {
        memo = new Integer[word1.length() + 1][word2.length() + 1];
        return minDistanceRecur(word1, word2, word1.length(), word2.length());
    }

    int minDistanceRecur(
        String word1,
        String word2,
        int word1Index,
        int word2Index
    ) {
        if (word1Index == 0) {
            return word2Index;
        }
        if (word2Index == 0) {
            return word1Index;
        }
        if (memo[word1Index][word2Index] != null) {
            return memo[word1Index][word2Index];
        }
        int minEditDistance = 0;
        if (word1.charAt(word1Index - 1) == word2.charAt(word2Index - 1)) {
            minEditDistance = minDistanceRecur(
                word1,
                word2,
                word1Index - 1,
                word2Index - 1
            );
        } else {
            int insertOperation = minDistanceRecur(
                word1,
                word2,
                word1Index,
                word2Index - 1
            );
            int deleteOperation = minDistanceRecur(
                word1,
                word2,
                word1Index - 1,
                word2Index
            );
            int replaceOperation = minDistanceRecur(
                word1,
                word2,
                word1Index - 1,
                word2Index - 1
            );
            minEditDistance = Math.min(
                insertOperation,
                Math.min(deleteOperation, replaceOperation)
            ) +
            1;
        }
        memo[word1Index][word2Index] = minEditDistance;
        return minEditDistance;
    }
}

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