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

😎 Решение:

public class Solution {
    public int MinDistance(string word1, string word2) {
        int?[][] memo = new int ?[word1.Length + 1][];
        for (int i = 0; i <= word1.Length; i++)
            memo[i] = new int?[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].Value;
            int minEditDistance = 0;
            if (word1[word1Index - 1] == word2[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;
        }
    }
}

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