```
class Solution {
public:
int minDistance(string word1, string word2) {
if(word1.empty()) return word2.length();
if(word2.empty()) return word1.length();
int len1 = word1.length(), len2 = word2.length();
int distance[len1+1][len2+1];
memset(distance, 0, sizeof(int)*(len1+1)*(len2+1));
for(int i = 0; i <= len1; ++i) distance[i][0] = i;
for(int i = 0; i <= len2; ++i) distance[0][i] = i;
for(int i = 1; i <= len1; ++i){
for(int j = 1; j <= len2; ++j){
if(word1[i-1] == word2[j-1]) distance[i][j] = distance[i-1][j-1];
else distance[i][j] = min(distance[i-1][j], min(distance[i][j-1], distance[i-1][j-1]))+1;
}
}
return distance[len1][len2];
}
};
```