```
// O(n^2) time, O(n^2) space
// can be optimized with O(n) space --> only keep one row because we only need the previous row to update the current row
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) return -1;
if (word1.length() == 0) return word2.length();
if (word2.length() == 0) return word1.length();
int l1 = word1.length();
int l2 = word2.length();
// minDist[i][j] represents the min distance between the substring(0, i) of word1 and the substring(0, j) of word2
int[][] minDist = new int[l1][l2];
// initialize
minDist[0][0] = word1.charAt(0) == word2.charAt(0) ? 0 : 1;
for (int i = 1; i < l1; i++) {
if (minDist[i - 1][0] != i || word1.charAt(i) == word2.charAt(0)) {
minDist[i][0] = i;
} else{
minDist[i][0] = i + 1;
}
}
for (int i = 1; i < l2; i++) {
if (minDist[0][i - 1] != i || word2.charAt(i) == word1.charAt(0)) {
minDist[0][i] = i;
} else{
minDist[0][i] = i + 1;
}
}
// DP
for (int i = 1; i < l1; i++) {
for (int j = 1; j < l2; j++) {
// eg. The distance between "ABCE" and "BDE" is the same as distance between "AB" and "BD"
if (word1.charAt(i) == word2.charAt(j)) {
minDist[i][j] = minDist[i - 1][j - 1];
} else {
// The min distance from s1 to s2 is either: eg. s1="ABCE", s2="BDF"
// deletion: min[i-1][j] + 1 1 + "ABC"- > "BDF" (1 represents deleting 'E' from "ABCE")
// insertion: min [i] [j-1] + 1 1 + "ABCE" -> "BD"
// insert 'F' to s1 is equivalent to delete 'F' from s2
// replacement: min[i-1][j-1] + 1
minDist[i][j] = Math.min(Math.min(minDist[i - 1][j], minDist[i][j - 1]), minDist[i - 1][j - 1]) + 1;
}
}
}
return minDist[l1 - 1][l2 - 1];
```