Simple java solution implement algorithm from text book


  • 0
    Y

    simple algorithm follow by
    E(i,j) = min{1+E(i-1,j),1+E(i,j-1),diff(i,j)+E(i-1,j-1)}

    The solution is enhanced with cache so it can be accepted without TLE

    public class Solution {
    
    public int minDistance(String word1, String word2) {
        
        if(word1.length() ==0 && word2.length() !=0)
        {
            return word2.length();
        }
        if(word1.length()!=0 && word2.length() ==0)
        {
            return word1.length();
        }
        int[][] mem = new int[word1.length()][word2.length()];
        for(int[] row : mem) Arrays.fill(row,-1);
        return editdistance(word1,word1.length()-1,word2,word2.length()-1,mem);
    }
    public int editdistance(String word1,int i,String word2,int j,int[][] mem)
    {
        if(i ==-1 && j == -1) return 0;
        if(j == -1) return i+1;
        if(i == -1) return j+1;
        if(mem[i][j]!=-1) return mem[i][j];
        int a = 1+editdistance(word1,i-1,word2,j,mem);
        int b = 1+editdistance(word1,i,word2,j-1,mem);
        int c = word1.charAt(i)==word2.charAt(j)?editdistance(word1,i-1,word2,j-1,mem):1+editdistance(word1,i-1,word2,j-1,mem);
        int minDistance = Math.min(a,Math.min(b,c));
        mem[i][j] = minDistance;
        return minDistance;
    }
    

    }


Log in to reply
 

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