```
public class Solution {
public int minDistance(String word1, String word2) {
if (word1.isEmpty()) return word2.length();
if (word2.isEmpty()) return word1.length();
int rows = word1.length();
int cols = word2.length();
int[][] m = new int[rows][cols];
// m[i][j] is the length of the longest common subsequence of word1.substring(0, i+1) and word2.substring(0, j+1)
m[0][0] = word1.charAt(0) == word2.charAt(0) ? 1 : 0;
for (int r=1; r<rows; ++r) {
m[r][0] = word1.charAt(r) == word2.charAt(0) ? 1 : m[r-1][0];
}
for (int c=1; c<cols; ++c) {
m[0][c] = word2.charAt(c) == word1.charAt(0) ? 1 : m[0][c-1];
}
for (int r=1; r<rows; ++r) {
for (int c=1; c<cols; ++c) {
if (word1.charAt(r) == word2.charAt(c)) {
m[r][c] = m[r-1][c-1] + 1;
} else {
m[r][c] = Math.max(m[r-1][c], m[r][c-1]);
}
}
}
int common = m[rows-1][cols-1];
return rows + cols - 2 * common;
}
}
```