题目描述
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
- 思路
给定两个字符串，问通过插入、删除、替换一个字符，最少几次操作可以使得两个字符串相等。
动态规划，通过最优子结构和重叠子问题求解。令 F(i, j)表示使第一个字符串的前 i 个与第二个字符串的前 j 个相等时的最小操作数。
则当 s1[i] == s2[j] 时，说明s1的前 i+1 个字符与s2的前 j+1个字符一样，则不需要变换，即 F(i, j) = F(i-1, j-1)；
否则，必须需要一步操作达到当前相等。以 "ab" 到 "abc"为例，该最优解为： min{"a" 到 "abc"的最优解, "ab" 到 "ab"的最优解，"a" 到 "ab" 的最优解 } + 1，所以该情况递推公式为：F(i, j) = min{F(i - 1, j), F(i, j - 1),F(i - 1, j - 1) } + 1（对应的三种操作）
注意需要对空字符变换的初始化，否则影响后续的操作
参考链接
public class Solution {
public int minDistance(String word1, String word2) {
if(word1 == null && word2 == null)
return -1;
if(word1 == null)
return word2.length();
if(word2 == null)
return word1.length();
if(word1.equals(word2))
return 0;
int len1 = word1.length();
int len2 = word2.length();
int[][] f = new int[len1+1][len2+1];
//处理存在非null的空串情况，方便后续使用
for(int i=0; i<=len2; i++)
f[0][i] = i;
for(int i=0; i<=len1; i++)
f[i][0] = i;
for(int i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){
if(word1.charAt(i-1) == word2.charAt(j-1)){
f[i][j] = f[i-1][j-1];
}else{
f[i][j] =
Math.min(f[i-1][j-1], Math.min(f[i][j-1], f[i-1][j])) + 1;
}
}
}
return f[len1][len2];
}
}
