```
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// DP table: min edits it takes to convert first i chars of word1 -> to first j chars of word2
// _ a b c d e f
// _ 0 1 2 3 4 5 6
// b 1 1 2 3 4 5 6 "b" -> "a", "b" -> "ab", "b" -> "abc", "b" -> "abcd"...
// c 2 "cb" -> "a", "cb" -> "ab", "cb" -> "abc"....
// e 3
// f 4 "bcef" -> "a", "bcef" -> "ab", ..."bcef" -> "abcdef"
// Comparing j-col word B to achieve i-row word A, action on B
int[][] edits = new int[m + 1][n + 1];
// first row/col, # edits to create word from scratch ""; num edits = # char
for (int i = 0; i <= m; i++) {
edits[i][0] = i;
}
for (int j = 0; j <= n; j++) {
edits[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i-1) == word2.charAt(j-1)) {
// no edits needed; "abcd" -> "abcde" = "bc" -> "bce" same as prev state A, B adding same char
edits[i][j] = edits[i-1][j-1];
} else {
// same as achieving the prev str state, "abcd" vs "bce" insert e onto B only, but using 1 more
// op to achieve it
int add = edits[i][j-1] + 1;
// same as achieving the prev str state, "abcde" vs "bc" del e on B, but using 1 more op to achieve it
int del = edits[i-1][j] + 1;
// same as prev A, B add 1 char to both, replace: "abc" -> "abcd" = "bc" -> "bcD"
int replace = edits[i-1][j-1] + 1;
int min = Math.min(add, del);
min = Math.min(min, replace);
edits[i][j] = min; // take min of compare all 3 possible changes, to achieve curr state
}
}
}
return edits[m][n];
}
```