Share my bottom up DP solution in Java


  • 0
    J
    public class Solution {
        public int minDistance(String word1, String word2) {
            if (word1.isEmpty()) return word2.length();
            if (word2.isEmpty()) return word1.length();
           
            int rows = word1.length();
            int cols = word2.length();
            int[][] m = new int[rows][cols];
            
            // m[i][j] is the length of the longest common subsequence of word1.substring(0, i+1) and word2.substring(0, j+1)
            m[0][0] = word1.charAt(0) == word2.charAt(0) ? 1 : 0;
            for (int r=1; r<rows; ++r) {
                m[r][0] = word1.charAt(r) == word2.charAt(0) ? 1 : m[r-1][0];
            }
            for (int c=1; c<cols; ++c) {
                m[0][c] = word2.charAt(c) == word1.charAt(0) ? 1 : m[0][c-1];
            }
            for (int r=1; r<rows; ++r) {
                for (int c=1; c<cols; ++c) {
                    if (word1.charAt(r) == word2.charAt(c)) {
                        m[r][c] = m[r-1][c-1] + 1;
                    } else {
                        m[r][c] = Math.max(m[r-1][c], m[r][c-1]);
                    }
                }
            }
            int common = m[rows-1][cols-1];
            return rows + cols - 2 * common;
        }
    }
    

Log in to reply
 

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