给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
思路:动态规划
1.状态定义
dp[i][j]表示把word1中0-i的子串变为word2中0-j的子串
2.初始化二维数组,容量加1保存初始值dp[0] = 0;
int[][] dp = new int[m + 1][n + 1];
3.状态方程
(1)如果word1[i] == word2[j],那么dp[i][j] = dp[i - 1][j - 1]
(2)否则,dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i][j])
4.返回dp[m][n]
public int miniDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
if (m == 0 || n == 0) {
return m + n;
}
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i < m + 1; i++) {
dp[i][0] = i;
}
for (int j = 0; j < n + 1; j++) {
dp[0][j] = j;
}
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
continue;
}
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
}
return dp[m][n];
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)