13 ms java dp solution with explanation


  • 1
    L

    dynamic programming

    a1...n -> b1...m have three ways

    1. a1...n-1 -> b1...m, delete an => distance[i+1][j+1] = distance[i][j+1] + 1

    2. a1...n -> b1...m-1, delete bm => distance[i+1][j+1] = distance[i+1][j] + 1

    3. a1..n-1 -> b1...m-1, replace an-1 to bm-1 => distance[i+1][j+1] = distance[i][j] + cost

    cost = a[i]==b[j]?0:1

    public class Solution {

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

    }


Log in to reply
 

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