代码: 第一个版本,通过91%给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少 *** 作数。
你可以对一个单词进行如下三种 *** 作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
class Solution {
public int minDistance(String word1, String word2) {
//dp
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1][len2];
if(len1==0 || len2==0)
return len1==0?len2:len1;
if(word1.charAt(0)==word2.charAt(0))
dp[0][0]=0;
else
dp[0][0]=1;
for(int i=1;i<len1;i++){
dp[i][0]=dp[i-1][0]+1;//插入一个数即可
}
for(int i=1;i<len2;i++){
dp[0][i]=dp[0][i-1]+1;
}
for(int i=1;i<len1;i++)
for(int j=1;j<len2;j++){
char c1=word1.charAt(i);
char c2 = word2.charAt(j);
if(c1==c2){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1; //删除,插入,替换一个
}
}
return dp[len1-1][len2-1];
}
}
第二个版本,通过100%
class Solution {
public int minDistance(String word1, String word2) {
//dp
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i=1;i<=len1;i++){
dp[i][0]=dp[i-1][0]+1;//插入一个数即可
}
for(int i=1;i<=len2;i++){
dp[0][i]=dp[0][i-1]+1;
}
for(int i=1;i<=len1;i++)
for(int j=1;j<=len2;j++){
char c1=word1.charAt(i-1);
char c2 = word2.charAt(j-1);
if(c1==c2){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1; //删除,插入,替换一个
}
}
return dp[len1][len2];
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)