Question

link

Stats

Frequency	3
Difficulty	4
Adjusted Difficulty	3
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a difficult DP problem. A lot of people said in their blog that they spent tons of time on this question.

Solution

I posted below a very standard solution. The unconventional part of this solution is instead of declaring DP array of m*n size, I must declare it (m+1)*(n+1) size, where dp[i][j] denotes the distance of 2 strings that ends with (i)th and (j)th char respectively.

The rest of the code is easy to understand.

Code

my code

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();

    int[][] dp = new int[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int i = 0; i <= n; i++) {
        dp[0][i] = i;
    }
    for (int a = 1; a <= m; a++) {
        char aa = word1.charAt(a-1);
        for (int b = 1; b <= n; b++) {
            char bb = word2.charAt(b-1);
            if (aa == bb) 
                dp[a][b] = dp[a-1][b-1];
            else {
                int t1 = dp[a-1][b-1] + 1;
                int t2 = dp[a][b-1] + 1;
                int t3 = dp[a-1][b] + 1;
                dp[a][b] = Math.min(Math.min(t1, t2), t3);
            }
        }
    }
    return dp[m][n];
}