編輯距離 dp

Problem: You are given two strings s1 and s2 of length M and N respectively. You can perform following operations on the string.

問題：給您兩個長度分別為M和N的字符串s1和s2 。 您可以對字符串執行以下操作。

1. Insert a character at any position

   在任意位置插入字符

2. Delete a character at any position

   刪除任意位置的字符

3. Replace a character with any character at any position

   用任意位置的任何字符替換字符

Find minimum number of ways to convert s1 into s2 using above operation only.

僅使用上述操作找出將s1轉換為s2的最小方法。

Constraints:

限制條件：

1 <= N <= 2000
1 <= M <= 2000

Example:

例：

    Sample Input 1:
abcde
bcdae
Sample Output 1:
2
Sample Input 2:
dacef
cdafe
Sample Output 2:
3

Explanation of the problem:

問題說明：

In the first sample provided above, we can delete a from s1 and insert it before e in s1. So, there are two steps.

在上面提供的第一個示例中，我們可以從s1中刪除a并將其插入s1中的 e之前。 因此，有兩個步驟。

Solution:

解：

Before proceeding to the solution we can see that the recursive solution will be hard to implement so we will proceed to the dynamic programming approach. In this approach, the j^th cell of i^th row represents the minimum number of changes needed to change s1(i^th index to end) and s2(j^th index to end). Now if an i^th character of s1 is equal to a j^th character of s2 then we don’t have to take care of that character as it is already same so pick up the right-bottom diagonal value. If characters are not equal then we can delete the i^th character of the s1 or j^th character of s2, replace the i^th character of s1 with the j^th character of s2 or vice versa and move on to the right bottom corner. In this case, we also have to add 1 as deletion, replacement is considered as a step.

在繼續解決方案之前，我們可以看到遞歸解決方案將很難實現，因此我們將繼續使用動態編程方法。 在這種方法中， ^第 i行的^第 j ^個單元表示更改s1( ^第 i ^個索引到結束)和s2( ^第 j ^個索引到結束)所需的最小更改次數。 現在，如果s1的^第 i ^個字符等于s2的^第 j ^個字符，那么我們就不必照顧這個字符了，因為它已經是相同的了，所以選擇右下角的對角線值。 如果字符不相等，那么我們可以刪除s1的^第 i ^個字符或s2的^第 j ^個字符，將s1的^第 i ^個字符替換為s2的^第 j ^個字符，反之亦然，然后移至右下角。 在這種情況下，我們還必須添加1作為刪除，替換被視為一個步驟。

Algorithm:

算法：

1. Create dp matrix in which j^th cell of i^th row represents the minimum number of ways to change the string s1 (from i^th index to last) and string s2 (j^th index to last).

   創建dp矩陣，其中^第 i行的^第 j ^個單元格表示更改字符串s1 (從^第 i ^個索引到最后一個)和字符串s2 ( ^第 j ^個索引到最后一個)的最小方式。

2. One extra row and col are taken to build to include blank string also.

   還需要多一行和col來構建以包括空白字符串。

3. If s1 is blank and s2 is full we have to initialize this condition so initializing this condition doing the same thing for vice versa case.

   如果s1為空白，而s2為滿，則必須初始化此條件，因此對這種情況進行初始化的情況與之相反。

4. Start filling dp matrix from the N^th row and M^th column (right to left and down to up).

   開始從^第 N行和M填充DP矩陣^列 (從右到左，下到上)。

5. Find the answer of each row by using dp relations.

   通過使用dp關系找到每一行的答案。

6. If i^th character of s1 is same as a j^th character of s2 then store the right-bottom value.

   如果I S1的^個字符是相同的^第 j ^個 S2的字符然后存儲右下角值。

7. Otherwise, take the minimum of downward adjacent, rightward adjacent, bottom-right adjacent value and add 1 to it and store the answer.

   否則，取下相鄰，右相鄰，右下相鄰值中的最小值，并將其加1并存儲答案。

8. Store the answer in a j^th cell of an i^th row.

   將答案存儲在^第 i行的^第 j ^個單元格中。

The time complexity of the above code is O (N * M).

上面代碼的時間復雜度是O(N * M)。

使用動態編程(DP)編輯距離的C ++代碼 (C++ Code for Edit Distance using Dynamic Programming (DP))

#include <iostream>
#include <math.h>
using namespace std;
// function for finding edit distance
int editDistance(string s1, string s2){
// dp matrix for storing the values
int dp[s1.length() + 1][s2.length() + 1] = {0};
int counter = 0;
// loops are used to store some values necessary for dp relations as 
// we can initialize all values to 0 in this case
for(int row = s1.length();row>=0;row--){
dp[row][s2.length()] = counter;
counter++;
}
counter = 0;
for(int col = s2.length();col>=0;col--){
dp[s1.length()][col] = counter;
counter++;
}
// filling the dp matrix 
for(int row = s1.length()-1;row>=0;row--){
for(int col = s2.length() - 1;col>=0;col--){
// if rowth character of s1 is same as colth character of s2 
// then store diagonally right-bottom shifted value
if(s1[row] == s2[col]){
dp[row][col] = dp[row+1][col+1];
}
// otherwise, take minimum of adjacent downward, adjacent rightward, 
// diagonally rigth-bottom value and add 1 to it and store that value
else{
dp[row][col] = min(dp[row+1][col], min(dp[row][col+1], dp[row+1][col+1])) + 1;
}
}
}
return dp[0][0];
}
// driver function to test the code
int main() {
string s1,s2;
cin >> s1 >> s2;
cout << s1 << "\n" << s2 << endl;
cout<< editDistance(s1, s2);
return 0;
}

Output

輸出量

abcde
bcdae
abcde
bcdae
2   

翻譯自: https://www.includehelp.com/algorithms/edit-distance-using-dynamic-programming.aspx

編輯距離 dp