class Solution {
public:
int minDistance(string word1, string word2) {
if (word1 == word2) return 0;
if (word1.empty()) return word2.size();
if (word2.empty()) return word1.size();
int row = word1.size();
int col = word2.size();
vector<vector<int>> dp(row+1, vector<int>(col+1,0));
for (int i=0; i<=row; ++i) {
for (int j=0; j<=col; ++j) {
if (i==0 || j==0) {
dp[i][j] = max(i, j);
} else if (word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;
}
}
}
return dp[row][col];
}
};
