72. Edit Distance
LeetCode
medium
оригинал: C#
#array
#csharp
#dynamic-programming
#leetcode
#math
#medium
#recursion
#string
Даны два слова 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')
C# решение
сопоставлено/оригинал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;
}
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int MinDistance(string word1, string word2) {
int?[][] memo = new int ?[word1.size() + 1][];
for (int i = 0; i <= word1.size(); i++)
memo[i] = new int?[word2.size() + 1];
return MinDistanceRecur(word1, word2, word1.size(), word2.size());
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 =
min(insertOperation,
min(deleteOperation, replaceOperation)) +
1;
}
memo[word1Index][word2Index] = minEditDistance;
return minEditDistance;
}
}
}Java решение
сопоставлено/оригинал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;
}
}JavaScript решение
сопоставлено/оригинал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);
};Python решение
сопоставлено/оригиналclass Solution:
def minDistance(self, word1: str, word2: str) -> int:
memo = [
[None for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)
]
def minDistanceRecur(word1, word2, word1Index, word2Index):
if word1Index == 0:
return word2Index
if word2Index == 0:
return word1Index
if memo[word1Index][word2Index] is not None:
return memo[word1Index][word2Index]
if word1[word1Index - 1] == word2[word2Index - 1]:
minEditDistance = minDistanceRecur(
word1, word2, word1Index - 1, word2Index - 1
)
else:
insertOperation = minDistanceRecur(
word1, word2, word1Index, word2Index - 1
)
deleteOperation = minDistanceRecur(
word1, word2, word1Index - 1, word2Index
)
replaceOperation = minDistanceRecur(
word1, word2, word1Index - 1, word2Index - 1
)
minEditDistance = (
min(insertOperation, deleteOperation, replaceOperation) + 1
)
memo[word1Index][word2Index] = minEditDistance
return minEditDistance
return minDistanceRecur(word1, word2, len(word1), len(word2))Go решение
сопоставлено/оригиналfunc minDistance(word1 string, word2 string) int {
memo := make([][]int, len(word1)+1)
for i := range memo {
memo[i] = make([]int, len(word2)+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
min := func(a, b, c int) int {
if a < b {
if a < c {
return a
}
return c
}
if b < c {
return b
}
return c
}
var minDistanceRecur func(word1, word2 string, word1Index, word2Index int) int
minDistanceRecur = func(word1, word2 string, word1Index, word2Index int) int {
if word1Index == 0 {
return word2Index
}
if word2Index == 0 {
return word1Index
}
if memo[word1Index][word2Index] != -1 {
return memo[word1Index][word2Index]
}
var minEditDistance int
if word1[word1Index-1] == word2[word2Index-1] {
minEditDistance = minDistanceRecur(
word1,
word2,
word1Index-1,
word2Index-1,
)
} else {
insertOperation := minDistanceRecur(word1, word2, word1Index, word2Index-1)
deleteOperation := minDistanceRecur(word1, word2, word1Index-1, word2Index)
replaceOperation := minDistanceRecur(word1, word2, word1Index-1, word2Index-1)
minEditDistance = min(insertOperation, deleteOperation, replaceOperation) + 1
}
memo[word1Index][word2Index] = minEditDistance
return minEditDistance
}
return minDistanceRecur(word1, word2, len(word1), len(word2))
}Algorithm
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 для будущего использования.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.