将字符串 1 转换为字符串 2 所需的最小编辑次数
问题陈述就好像我们给两个字符串 str1 和 str2 然后在 str1 上可以执行多少最小操作数就可以转换为 str2。操作可以是:
- 插入
- 去掉
- 更换
例如
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 .So,我们的数组看起来像
(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)