Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
b) Delete a character
c) Replace a character
Solution:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<vector<int> > inner(m+1,vector<int>(n+1, 0));
for(int i=0;i<=m;i++)
{
inner[i][0] = i;//word2 is empty
}
for(int i=0;i<=n;i++)
{
inner[0][i] = i; //word1 is empty
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(word1[i-1] == word2[j-1])
{
inner[i][j] = inner[i-1][j-1];
}
else
{
int ins = inner[i][j-1]+1; //insert
int del = inner[i-1][j]+1; //delete
int rep = inner[i-1][j-1]+1; //replace
inner[i][j] = min(ins, min(del, rep));
}
}
}
return inner[m][n];
}
No comments:
Post a Comment