Edit Distance java efficient approach dp


  • 0
    N

    ''' class Solution {
    public int minDistance(String word1, String word2) {
    if(word1==null&&word2==null)return 0;
    if(word2==null)return word1.length();
    if(word1==null)return word2.length();
    int l1=word1.length();
    int l2=word2.length();
    int dp[][]=new int[l1+1][l2+1];
    for(int i=0;i<=l1;i++)
    {

            for(int j=0;j<=l2;j++)
            {
                if(i==0)dp[i][j]=j;
                else if(j==0)dp[i][j]=i;
               else if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }
                else{
                       int min1=Math.min(dp[i-1][j-1],dp[i-1][j]);
                       int min2=1+Math.min(min1,dp[i][j-1]);
                    dp[i][j]=min2;
                }
        }
    }
            return dp[l1][l2];
    }
    

    } '''


Log in to reply
 

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