Постановка задачи
Имея две строки word1 и word2, верните минимальное количество операций, необходимых для преобразования слова1 в слово2.
Над словом разрешены следующие три операции:
- Вставить символ
- Удалить персонажа
- Заменить символ
Постановка задачи взята с: https://leetcode.com/problems/edit-distance
Пример 1:
Input: word1 = 'horse', word2 = 'ros'
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')Пример 2:
Input: word1 = 'intention', word2 = 'execution'
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')Ограничения:
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters.Объяснение
Согласно Википедии:
Расстояние редактирования — это строковая метрика, т. е. способ количественной оценки того, насколько две строки (например, слова) отличаются друг от друга, который измеряется путем подсчета минимального количества операций, необходимых для преобразования одной строки в другую.
Расстояния редактирования находят применение в обработке естественного языка, где автоматическая коррекция орфографии может определять возможные исправления для слова с ошибкой, выбирая слова из словаря с небольшим расстоянием до рассматриваемого слова. В биоинформатике его можно использовать для количественной оценки сходства последовательностей ДНК, которые можно рассматривать как цепочки букв A, C, G и T.
В разных определениях расстояния редактирования используются разные наборы строковых операций. Операции расстояния Левенштейна — это удаление, вставка или замена символа в строке. Термин расстояние Левенштейна, являющийся наиболее распространенным показателем, часто используется взаимозаменяемо с расстоянием редактирования.
В этом сообщении блога мы обсудим три решения проблемы редактирования расстояния. Мы начнем с грубой силы и попробуем оптимизировать решение с помощью динамического программирования.
Подход грубой силы
Грубый подход основан на рекурсии. Мы думаем о более мелких подзадачах, которые можно легко решить. Мы рекурсивно просматриваем входную последовательность и определяем, какая операция Insert, Delete или Replace будет стоить минимум.
Мы рассматриваем i и j как указатели на слово1 и слово2 соответственно. Если первый символ обеих строк одинаков, мы рекурсивно используем длины i + 1 и j + 1. Если символы разные, мы выполним все три операции над этим символом. Мы вычисляем, какая стоимость операции минимальна.
Фрагмент C++ этого подхода выглядит следующим образом:
int editDistance(string word1, string word2) {
if (word1.length() == 0)
return word2.length();
if (word2.length() == 0)
return word1.length();
return match(word1, word2, 0, 0);
}
int match(string s1, string s2, int i, int j) {
if (s1.length() == i)
return s2.length() - j;
if (s2.length() == j)
return s1.length() - i;
int result;
if (s1[i] == s2[j]) {
result = match(s1, s2, i + 1, j + 1);
} else {
int insertChar = match(s1, s2, i, j + 1);
int deleteChar = match(s1, s2, i + 1, j);
int substituteChar = match(s1, s2, i + 1, j + 1);
result = min(insertChar, deleteChar, substituteChar) + 1;
}
return result
}
Временная сложность этого подхода составляет O(3^n). Пространственная сложность равна O(m), где m — пространство стека дерева рекурсии.
Динамическое программирование: подход к мемоизации
Если мы посмотрим на стек рекурсии в подходе грубой силы, мы обнаружим, что многие подзадачи перекрываются. Когда мы вычисляем минимальное значение для i-го и j-го индексов слов word1 и word2 соответственно, мы сохраняем значение в кэш-массиве, чтобы его можно было использовать при необходимости.
Предполагая, что мы знаем расстояние редактирования двух строк до индексов i и j. Затем мы можем написать
editDistance(i + 1, j + 1) = 1 + min (editDistance(i, j + 1), editDistance(i + 1, j), editDistance(i, j))- Мы проверяем, равны ли символы в word1[i] слову2[j], затем ищем cache[i + 1][j + 1].
- В противном случае мы берем минимум cache[i + 1][j], cache[i][j + 1], cache[i][j] и добавляем к нему 1 и сохраняем результат в cache[i + 1][ j + 1].
Фрагмент C++ этого подхода выглядит следующим образом:
int editDistance(string word1, string word2) {
int cache[word1.length][word2.length];
for (int i = 0; i < word1.length; i++) {
for (int j = 0; j < word2.length; j++) {
cache[i][j] = -1;
}
}
return match(word1, word2, 0, 0, cache);
}
int match(string s1, string s2, int i, int j, int[][] cache){
if (s1.size() == i)
return s2.size() - j;
if (s2.size() == j)
return s1.size() - i;
if (cache[i][j] != -1) {
return cache[i][j];
}
if (s1[i] == s2[j]) {
cache[i][j] = match(s1, s2, i + 1, j + 1, cache);
} else {
int insertChar = match(s1, s2, i, j + 1, cache);
int deleteChar = match(s1, s2, i + 1, j, cache);
int replaceChar = match(s1, s2, i + 1, j + 1, cache);
cache[i][j] = min(insertChar, deleteChar, replaceChar) + 1;
}
return cache[i][j];
}
Временная сложность этого подхода составляет O(n²). Пространственная сложность O(n²).
Динамическое программирование: табулирующий подход
Подход табуляции работает восходящим образом по сравнению с подходом мемоизации сверху вниз. При восходящем подходе при вычислении editDistance для i и j мы сначала вычисляем минимум из
editDistance(i - 1, j)
editDistance(i, j - 1)
editDistance(i - 1, j - 1)Давайте проверим алгоритм, чтобы понять его ясно.
Алгоритм
- set m = word1.length()
n = word2.length()
- initialize vector<vector<int>> dp(m + 1, vector<int>(n + 1))
- loop for i = 0; i <= m; i++
- set dp[i][0] = i
- for end
- loop for j = 0; j <= n; j++
- set dp[0][j] = j
- for end
- loop for i = 1; i <= m; i++
- loop for j = 1; j <= n; j++
- if word1[i - 1] == word2[j - 1]
- set dp[i][j] = dp[i - 1][j - 1]
- else
- set dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
- if end
- for end
- for end
- return dp[m][n]Временная сложность этого подхода составляет O(n²). Пространственная сложность O(n²).
Давайте проверим наши решения на C++, Golang и Javascript.
С++ решение
class Solution {
public:
int editDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]});
}
}
}
return dp[m][n];
}
};
Голанг решение
func editDistance(word1 string, word2 string) int {
m , n := len(word1), len(word2)
dp := make([][]int, m + 1)
for i := 0; i < m + 1; i++ {
dp[i] = make([]int, n + 1)
}
for i := 0; i <= m; i++ {
dp[i][0] = i
}
for j := 0; j <= n; j++ {
dp[0][j] = j
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if word1[i - 1] == word2[j - 1] {
dp[i][j] = dp[i - 1][j - 1]
} else {
dp[i][j] = 1 + min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1])
}
}
}
return dp[m][n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
JavaScript-решение
var editDistance = function(word1, word2) {
let m = word1.length;
let n = word2.length;
let dp = Array(m + 1).fill().map(() => Array(n + 1));
for (let i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (let j = 0; j <= n; j++) {
dp[0][j] = j;
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
};
Давайте проверим наш алгоритм на нескольких примерах, чтобы увидеть, как работает решение.
Input: word1 = 'horse'
word2 = 'ros'
Step 1: m = word1.length()
= 5
n = word2.length()
= 3
Step 2: vector<vector<int>> dp(m + 1, vector<int>(n + 1))
dp[6][4]
Step 3: loop for i = 0; i <= m; i++
dp[i][0] = i
for end
dp = [
[0, 0, 0, 0],
[1, 0, 0, 0],
[2, 0, 0, 0],
[3, 0, 0, 0],
[4, 0, 0, 0],
[5, 0, 0, 0],
]
Step 4: loop for j = 0; i <= n; i++
dp[0][j] = j
for end
dp = [
[0, 1, 2, 3],
[1, 0, 0, 0],
[2, 0, 0, 0],
[3, 0, 0, 0],
[4, 0, 0, 0],
[5, 0, 0, 0],
]
Step 5: loop for i = 1; i <= m
1 <= 5
true
loop for j = 1; j <= n
1 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[1 - 1] == word2[1 - 1]
word1[0] == word2[0]
'h' == 'r'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[1][1] = 1 + min(dp[1][1 - 1], dp[1 - 1][1], dp[1 - 1][1 - 1])
= 1 + min(dp[1][0], dp[0][1], dp[0][0])
= 1 + min(1, 1, 0)
= 1 + 0
= 1
j++
j = 2
loop for j <= n
2 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[1 - 1] == word2[2 - 1]
word1[0] == word2[1]
'h' == 'o'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[1][2] = 1 + min(dp[1][2 - 1], dp[1 - 1][2], dp[1 - 1][2 - 1])
= 1 + min(dp[1][1], dp[0][2], dp[0][1])
= 1 + min(1, 2, 1)
= 1 + 1
= 2
j++
j = 3
loop for j <= n
3 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[1 - 1] == word2[3 - 1]
word1[0] == word2[2]
'h' == 's'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[1][3] = 1 + min(dp[1][3 - 1], dp[1 - 1][3], dp[1 - 1][3 - 1])
= 1 + min(dp[1][2], dp[0][3], dp[0][2])
= 1 + min(2, 3, 2)
= 1 + 2
= 3
j++
j = 4
loop for j <= n
4 <= 3
false
dp = [
[0, 1, 2, 3],
[1, 1, 2, 3],
[2, 0, 0, 0],
[3, 0, 0, 0],
[4, 0, 0, 0],
[5, 0, 0, 0],
]
i++
i = 2
Step 6: loop for i <= m
2 <= 5
true
loop for j = 1; j <= n
1 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[2 - 1] == word2[1 - 1]
word1[1] == word2[0]
'o' == 'r'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[2][1] = 1 + min(dp[2][1 - 1], dp[2 - 1][1], dp[2 - 1][1 - 1])
= 1 + min(dp[2][0], dp[1][1], dp[1][0])
= 1 + min(2, 1, 1)
= 1 + 1
= 2
j++
j = 2
loop for j <= n
2 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[2 - 1] == word2[2 - 1]
word1[1] == word2[1]
'o' == 'o'
true
dp[i][j] = dp[i - 1][j - 1]
dp[2][2] = dp[2 - 1][2 - 1]
= dp[1][1]
= 1
j++
j = 3
loop for j <= n
3 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[2 - 1] == word2[3 - 1]
word1[1] == word2[2]
'o' == 's'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[2][3] = 1 + min(dp[2][3 - 1], dp[2 - 1][3], dp[2 - 1][3 - 1])
= 1 + min(dp[2][2], dp[1][3], dp[1][2])
= 1 + min(1, 3, 2)
= 1 + 1
= 2
j++
j = 4
loop for j <= n
4 <= 3
false
dp = [
[0, 1, 2, 3],
[1, 1, 2, 3],
[2, 2, 1, 2],
[3, 0, 0, 0],
[4, 0, 0, 0],
[5, 0, 0, 0],
]
i++
i = 3
Step 7: loop for i <= m
3 <= 5
true
loop for j = 1; j <= n
1 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[3 - 1] == word2[1 - 1]
word1[2] == word2[0]
'r' == 'r'
true
dp[i][j] = dp[i - 1][j - 1]
dp[3][1] = dp[3 - 1][1 - 1]
= dp[2][0]
= 2
j++
j = 2
loop for j <= n
2 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[3 - 1] == word2[2 - 1]
word1[2] == word2[1]
'r' == 'o'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[3][2] = 1 + min(dp[3][2 - 1], dp[3 - 1][2], dp[3 - 1][2 - 1])
= 1 + min(dp[3][1], dp[2][2], dp[2][1])
= 1 + min(0, 1, 2)
= 1 + 1
= 2
j++
j = 3
loop for j <= n
3 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[3 - 1] == word2[3 - 1]
word1[2] == word2[2]
'r' == 's'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[3][3] = 1 + min(dp[3][3 - 1], dp[3 - 1][3], dp[3 - 1][3 - 1])
= 1 + min(dp[3][2], dp[2][3], dp[2][2])
= 1 + min(0, 1, 1)
= 1 + 1
= 2
j++
j = 4
loop for j <= n
4 <= 3
false
dp = [
[0, 1, 2, 3],
[1, 1, 2, 3],
[2, 2, 1, 2],
[3, 2, 2, 2],
[4, 0, 0, 0],
[5, 0, 0, 0],
]
i++
i = 4
Step 8: loop for i <= m
4 <= 5
true
loop for j = 1; j <= n
1 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[4 - 1] == word2[1 - 1]
word1[3] == word2[0]
's' == 'r'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[4][1] = 1 + min(dp[4][1 - 1], dp[4 - 1][1], dp[4 - 1][1 - 1])
= 1 + min(dp[4][0], dp[3][1], dp[3][0])
= 1 + min(4, 2, 3)
= 1 + 2
= 3
j++
j = 2
loop for j <= n
2 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[4 - 1] == word2[2 - 1]
word1[3] == word2[1]
's' == 'o'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[4][2] = 1 + min(dp[4][2 - 1], dp[4 - 1][2], dp[4 - 1][2 - 1])
= 1 + min(dp[4][1], dp[3][2], dp[3][1])
= 1 + min(3, 2, 2)
= 1 + 2
= 3
j++
j = 3
loop for j <= n
3 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[4 - 1] == word2[3 - 1]
word1[3] == word2[2]
's' == 's'
true
dp[i][j] = dp[i - 1][j - 1]
dp[4][3] = dp[4 - 1][3 - 1]
= dp[3][2]
= 2
j++
j = 4
loop for j <= n
4 <= 3
false
dp = [
[0, 1, 2, 3],
[1, 1, 2, 3],
[2, 2, 1, 2],
[3, 2, 2, 2],
[4, 3, 3, 2],
[5, 0, 0, 0],
]
i++
i = 5
Step 9: loop for i <= m
5 <= 5
true
loop for j = 1; j <= n
1 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[5 - 1] == word2[1 - 1]
word1[4] == word2[0]
'e' == 'r'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[5][1] = 1 + min(dp[5][1 - 1], dp[5 - 1][1], dp[5 - 1][1 - 1])
= 1 + min(dp[5][0], dp[4][1], dp[4][0])
= 1 + min(5, 3, 4)
= 1 + 3
= 4
j++
j = 2
loop for j = 1; j <= n
2 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[5 - 1] == word2[2 - 1]
word1[4] == word2[1]
'e' == 'o'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[5][2] = 1 + min(dp[5][2 - 1], dp[5 - 1][2], dp[5 - 1][2 - 1])
= 1 + min(dp[5][1], dp[4][2], dp[4][1])
= 1 + min(4, 3, 3)
= 1 + 3
= 4
j++
j = 3
loop for j = 1; j <= n
3 <= 3
true
if word1[i - 1] == word2[j - 1]
word1[5 - 1] == word2[3 - 1]
word1[4] == word2[2]
'e' == 's'
false
else
dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]})
dp[5][3] = 1 + min(dp[5][3 - 1], dp[5 - 1][3], dp[5 - 1][3 - 1])
= 1 + min(dp[5][2], dp[4][3], dp[4][2])
= 1 + min(4, 2, 3)
= 1 + 2
= 3
j++
j = 4
loop for j = 1; j <= n
4 <= 3
false
dp = [
[0, 1, 2, 3],
[1, 1, 2, 3],
[2, 2, 1, 2],
[3, 2, 2, 2],
[4, 3, 3, 2],
[5, 4, 4, 3],
]
i++
i = 6
Step 10: loop for i <= m
6 <= 5
false
Step 11: return dp[m][n]
dp[5][3]
3
We return the answer as 3.Первоначально опубликовано на https://alkeshghorpade.me.
