```
class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.length();
int n2 = word2.length();
// application of dynamic programming
vector<vector<int>> DP;
DP.resize(n1+2);
int i, j;
for(i=0; i<=n1; i++)
DP[i].resize(n2+2, 10000000);
DP[0][0] = 0;
// DP[i][j] is minDistance(word1[0,...,i-1], word2[0,...,j-1])
for(i=0; i<=n1; i++)
{
for(j=0; j<=n2; j++)
{
if(i<n1)
DP[i+1][j] = min(DP[i+1][j], DP[i][j]+1);
// insert character for word2 or delete character for word1
if(j<n2)
DP[i][j+1] = min(DP[i][j+1], DP[i][j]+1);
// insert character for word1 or delete character for word2
if(i<n1 && j<n2)
{
if(word1[i] == word2[j])
DP[i+1][j+1] = min(DP[i+1][j+1], DP[i][j]);
else
DP[i+1][j+1] = min(DP[i+1][j+1], DP[i][j]+1); // replace a character
}
}
}
return DP[n1][n2];
}
};
```