Java solution same as minimum edit distance


  • 0
    C
    public int minDistance(String word1, String word2) {
            // 0 represents "" in row and col
            int[][] dp = new int[word1.length() + 1][word2.length() + 1];
            
            // number of deletion required to achieve "" in word1
            for(int i=0; i<dp.length; i++){
                dp[i][0] = i;
            }
            
            // number of deletion required to achieve "" in word2
            for(int i=0; i<dp[0].length; i++){
                dp[0][i] = i;
            }
            
            for(int i=1; i<dp.length; i++){
                char ch = word1.charAt(i-1);
                for(int j=1; j<dp[0].length; j++){
                    // if its a match check the sub string of word1(0,i-1) and word2(0,j-1)
                    if(ch == word2.charAt(j-1)){
                        dp[i][j] = dp[i-1][j-1];
                    }
                    // else take the minimum + 1
                    else{
                        dp[i][j] = 1 + Math.min(dp[i][j-1], dp[i-1][j]);
                    }
                }
            }
            
            // minimum result
            return dp[word1.length()][word2.length()];
        }
    

Log in to reply
 

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