9ms Beats 98% simple Java DP solution


  • 0
    C

    Used simple Dynamic programming with memoization.
    '''
    public class Solution {
    public int minDistance(String word1, String word2) {
    int memo[][]=new int[word1.length()][word2.length()];
    return minDistance(word1,word2,0,0,memo);
    }

    int minDistance(String word1,String word2,int i,int j,int [][]memo){
        if(i>=word1.length() && j>=word2.length())
            return 0;
        
        if(i>=word1.length() && j<word2.length()){
            return word2.length()-j;
        }
        
        if(j>=word2.length() && i<word1.length()){
            return word1.length()-i;
        }
        
        if(memo[i][j]!=0)
            return memo[i][j];
        if(word1.charAt(i)==word2.charAt(j))
            {
                memo[i][j]=minDistance(word1,word2,i+1,j+1,memo);
                return memo[i][j];
            } 
        
        int op1=minDistance(word1,word2,i+1,j,memo)+1;
        int op2=minDistance(word1,word2,i+1,j+1,memo)+1;
        int op3=minDistance(word1,word2,i,j+1,memo)+1;
        
        memo[i][j]= Math.min(op1,Math.min(op2,op3));
        return memo[i][j];
    }
    

    }
    '''


Log in to reply
 

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