share my concise JAVA DP solution


  • 0
    S
    public class Solution {
        public int minDistance(String word1, String word2) {
            if (word1 == null || word2 == null) {
                return Integer.MAX_VALUE;
            }
            int[][] m = new int[word1.length() + 1][word2.length() + 1];
            for (int i = 0; i < m.length; i++) {
                for (int j = 0; j < m[0].length; j++) {
                    if (i == 0) {
                        m[i][j] = j;
                        continue;
                    }
                    if (j == 0) {
                        m[i][j] = i;
                        continue;
                    }
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                        // do nothing
                        m[i][j] = m[i - 1][j - 1];
                    } else {
                        // compare replace and delete;
                        m[i][j] = Math.min(1 + m[i - 1][j - 1], 1 + m[i - 1][j]);
                        // compare with insert;
                        m[i][j] = Math.min(m[i][j], 1 + m[i][j - 1]);
                    }
                }
            }
            return m[word1.length()][word2.length()];
        }
    }
    

Log in to reply
 

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