Simple and clean Java DP solution with comments


  • 3
    J

    /**

    dp[i][j] denotes minimum distance between substring word1(0..i-1) and
    word2(0..j-1).

    The initialization:

    dp(i,0) = i (need i deletions), dp(0, j) =
    j (need j insertions).

    Recurrence relation:

    dp[i,j] = minimum of dp[i-1,j]+1, dp[i,j-1]+1 or dp[i-1][j-1]+delta,


    whereas delta = 0 if word1[i-1] == word2[j-1] or 1 if word1[i-1] != word2[j-1].


    */

    public int minDistance(String word1, String word2) {
    	int m = word1.length(), n = word2.length();
    
    	int[][] dp = new int[m + 1][n + 1];
    	for (int i = 0; i <= m; i++)
    		dp[i][0] = i;
    	for (int j = 0; j <= n; j++)
    		dp[0][j] = j;
    	for (int i = 1; i <= m; i++) {
    		for (int j = 1; j <= n; j++) {
    			int min = dp[i - 1][j - 1] + ((word1.charAt(i - 1) == word2.charAt(j - 1)) ? 0 : 1);
    			dp[i][j] = Math.min(min,
    					Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
    		}
    	}
    	return dp[m][n];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.