给定一个原串和目标串，能对源串进行如下操作： 1.在给定位置

[问答题]

给定一个原串和目标串，能对源串进行如下操作：
1.在给定位置插入一个字符
2.替换任意字符
3.删除任意字符
要求写一个程序，返回最少的操作数，使得源串进行这些操作后等于目标串。源串和目标串长度都小于2000。

AndyJee

class Solution {
public:
int minDistance(string word1, string word2) {
int m=word1.length();
int n=word2.length();
vector<vector<int> > distance(m+1,vector<int>(n+1));

for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(0==i){
distance[i][j]=j;
}
else if(0==j){
distance[i][j]=i;
}
else{
distance[i][j]=min(distance[i-1][j-1]+((word1[i-1]==word2[j-1])?0:1),
min(distance[i-1][j]+1,distance[i][j-1]+1)
);
}
}
}
return distance[m][n];
}
};

发表于 2015-04-14 23:00:07 回复(1)

牛客685442775号

public static int minOperationCount(String source, String target) { int m = source.length();  int n = target.length();  int[][] arr = new int[m+1][n+1];   for (int i =0; i < m+1;i++){
            arr[i][0] = i;  } for (int i =0; i < n+1;i++){
            arr[0][i] = i;  } for (int i = 1; i < m+1;i++){ for (int j = 1; j < n+1;j++){ if (source.charAt(i-1)== target.charAt(j-1)){
                    arr[i][j] = arr[i-1][j-1];  }else {
                    arr[i][j] = 1 + Math.min(arr[i-1][j-1],Math.min(arr[i-1][j],arr[i][j-1]));  }
            }
        } return arr[m][n]; }