题目描述
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
代码
class Solution {
public int minDistance(String word1, String word2) {
char[] p = (" "+word1).toCharArray();
char[] s = (" "+word2).toCharArray();
int n = word1.length(), m = word2.length();
int[][] f = new int[n+5][m+5];
for(int i=1; i<=n; i++) f[i][0] = i;
for(int i=1; i<=m; i++) f[0][i] = i;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
f[i][j] = Math.min(f[i-1][j]+1, f[i][j-1]+1);
if(p[i]==s[j]) f[i][j] = Math.min(f[i-1][j-1], f[i][j]);
else f[i][j] = Math.min(f[i-1][j-1]+1, f[i][j]);
}
}
return f[n][m];
}
}