algorithm
Изменение динамического алгоритма расстояния
Поиск…
Минимальные изменения, необходимые для преобразования строки 1 в строку 2
Оператор проблемы похож, если нам даны две строки str1 и str2, а затем сколько минимального количества операций может быть выполнено на str1, которое оно преобразует в str2.The Операции могут быть:
- Вставить
- Удалить
- замещать
Например
Input: str1 = "geek", str2 = "gesek"
Output: 1
We only need to insert s in first string
Input: str1 = "march", str2 = "cart"
Output: 3
We need to replace m with c and remove character c and then replace h with t
Для решения этой проблемы мы будем использовать 2D-массив dp [n + 1] [m + 1], где n - длина первой строки, а m - длина второй строки. Для нашего примера, если str1 является azcef, а str2 является abcdef, тогда наш массив будет dp [6] [7], и наш окончательный ответ будет сохранен в dp [5] [6].
(a) (b) (c) (d) (e) (f)
+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+
(a)| 1 | | | | | | |
+---+---+---+---+---+---+---+
(z)| 2 | | | | | | |
+---+---+---+---+---+---+---+
(c)| 3 | | | | | | |
+---+---+---+---+---+---+---+
(e)| 4 | | | | | | |
+---+---+---+---+---+---+---+
(f)| 5 | | | | | | |
+---+---+---+---+---+---+---+
Для dp [1] [1] мы должны проверить, что мы можем сделать, чтобы преобразовать a в a. Это будет 0. Для dp [1] [2] мы должны проверить, что мы можем сделать, чтобы преобразовать a в ab .It будет 1, потому что мы должны вставить b. После первой итерации наш массив будет выглядеть так:
(a) (b) (c) (d) (e) (f)
+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+
(a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(z)| 2 | | | | | | |
+---+---+---+---+---+---+---+
(c)| 3 | | | | | | |
+---+---+---+---+---+---+---+
(e)| 4 | | | | | | |
+---+---+---+---+---+---+---+
(f)| 5 | | | | | | |
+---+---+---+---+---+---+---+
Для итерации 2
Для dp [2] [1] мы должны проверить, что для преобразования az в a нам нужно удалить z , поэтому dp [2] [1] будет 1. Симологично для dp [2] [2] нам нужно заменить z с b , поэтому dp [2] [2] будет 1. После второй итерации будет выглядеть массив dp [] .
(a) (b) (c) (d) (e) (f)
+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+
(a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(z)| 2 | 1 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(c)| 3 | | | | | | |
+---+---+---+---+---+---+---+
(e)| 4 | | | | | | |
+---+---+---+---+---+---+---+
(f)| 5 | | | | | | |
+---+---+---+---+---+---+---+
Итак, наша формула будет выглядеть так:
if characters are same
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + Min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
После последней итерации наш массив dp [] будет выглядеть так:
(a) (b) (c) (d) (e) (f)
+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+
(a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(z)| 2 | 1 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(c)| 3 | 2 | 2 | 1 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+
(e)| 4 | 3 | 3 | 2 | 2 | 2 | 3 |
+---+---+---+---+---+---+---+
(f)| 5 | 4 | 4 | 2 | 3 | 3 | 3 |
+---+---+---+---+---+---+---+
Реализация на Java
public int getMinConversions(String str1, String str2){
int dp[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0)
dp[i][j] = j;
else if(j==0)
dp[i][j] = i;
else if(str1.charAt(i-1) == str2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
}
}
}
return dp[str1.length()][str2.length()];
}
Сложность времени
O(n^2)