Edit Distance
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
采用动态规划求解
1. d[0, j] = j;
2. d[i, 0] = i;
3. d[i, j] = d[i-1, j - 1] if A[i] == B[j]
4. d[i, j] = min(d[i-1, j - 1], d[i, j - 1], d[i-1, j]) + 1 if A[i] != B[j]
class Solution {
public:
int minDistance(string word1, string word2) {
int n1=word1.length();
int n2=word2.length();
if(n1==) return n2;
if(n2==) return n1;
//采用二维数组效率更高
//vector<vector<int> > dp(n1+1,vector<int>(n2+1));
int **dp=new int*[n1+];
for(int i=;i<n1+;i++)
{
dp[i]=new int[n2+];
}
dp[][]=;
for(int i=;i<=n1;i++)
{
dp[i][]=i;
}
for(int j=;j<=n2;j++)
{
dp[][j]=j;
}
for(int i=;i<=n1;i++)
{
for(int j=;j<=n2;j++)
{
if(word1[i-]==word2[j-])
{
dp[i][j]=dp[i-][j-];
}
else
{
dp[i][j]=min(dp[i-][j],min(dp[i][j-],dp[i-][j-]))+;
}
}
}
int result=dp[n1][n2];
for(int i=;i<n1+;i++)
{
delete[] dp[i];
}
return result;
}
};