Edit Distance

1public int minDistance(String word1, String word2) {
2    int m = word1.length();
3    int n = word2.length();
4    int[][] dp = new int[m + 1][n + 1];
5
6    // Initialize base cases
7    for (int i = 0; i <= m; i++) {
8        dp[i][0] = i;
9    }
10    for (int j = 0; j <= n; j++) {
11        dp[0][j] = j;
12    }
13
14    // Fill the dp table
15    for (int i = 1; i <= m; i++) {
16        for (int j = 1; j <= n; j++) {
17            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
18                dp[i][j] = dp[i - 1][j - 1];
19            } else {
20                dp[i][j] = 1 + Math.min(dp[i][j - 1],
21                                        Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
22            }
23        }
24    }
25
26    return dp[m][n];
27}