```
class Solution {
public:
int minDistance(string word1, string word2) {
if (word1.empty()) return word2.size();
if (word2.empty()) return word1.size();
int l1 = word1.size(),l2 = word2.size();
int step[l1+1][l2+1];
for (int i=0;i<=l2;i++) step[0][i] = i;
for (int i=1;i<=l1;i++) step[i][0] = i;
for (int i=1;i<=l1;i++){
for (int j=1;j<=l2;j++){
if (word1[i-1]==word2[j-1]) step[i][j]=step[i-1][j-1];
else {
step[i][j]=min(min(step[i-1][j-1],step[i-1][j]),step[i][j-1])+1;
}
}
}
return step[l1][l2];
}
};
```