leetcode編集距離
955 ワード
class Solution {
public:
int minDistance(string word1, string word2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int row=word1.length();
int col=word2.length();
vector< vector<int> > dis(row+1,vector<int>(col+1,0));
dis[0][0]=0;
for(int i=1;i<row+1;i++){
dis[i][0]=i;
}
for(int j=1;j<col+1;j++){
dis[0][j]=j;
}
for(int i=1;i<row+1;i++){
for(int j=1;j<col+1;j++){
int mindis=min(dis[i-1][j]+1,dis[i][j-1]+1);
assert(mindis>=1);
dis[i][j]=min(mindis,dis[i-1][j-1]+getDis(word1[i-1],word2[j-1]));
}
}
return dis[row][col];
}
private:
int getDis(char a,char b){
if(a==b)
return 0;
else
return 1;
}
};
難点:dis配列のrow colの下付きはstring中の位置がi-1の文字列を表す
例えば、dis【1】【1】はword 1【0】からword 2【0】までの編集距離である.