Java DP Accepted Solution


  • 2
    S

    The case which is difficult to deal with is when word1[i] != word2[j]. And it's min(opt[i-1,j],opt[i-1,j-1],opt[i,j-1])+1. Why? Because I could either replace one (opt[i-1,j-1]) or insert one (opt[i-1,j] or opt[i,j-1]). Hope that helps.

    public class Solution {
        public int minDistance(String word1, String word2) {
            int opt[][] = new int[word1.length()+1][word2.length()+1];
            // base case
            opt[0][0] = 0;
            for(int i = 0;i < word1.length();i++){opt[i+1][0] = i+1;}
            for(int j = 0;j < word2.length();j++){opt[0][j+1] = j+1;}
            
            //iteration
            for(int i = 0;i < word1.length();i++)
                for(int j = 0;j < word2.length();j++)
                    opt[i+1][j+1] = word1.charAt(i) == word2.charAt(j)?opt[i][j]:Math.min(Math.min(opt[i][j],opt[i+1][j]),opt[i][j+1])+1;
            
            return opt[word1.length()][word2.length()];
        }
    }

Log in to reply
 

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