Clear Java DP


  • 0
    L
    public class Solution {
        int[][] dp;
        public int minDistance(String word1, String word2) {
            int len1 = word1.length();
            int len2 = word2.length();
            dp = new int[len1 + 1][len2 + 1];
            for (int i = 0; i < len1 + 1; i++) {
                for (int j = 0; j < len2 + 1; j++) {
                    dp[i][j] = -1;
                }
            }
            char[] chars1 = word1.toCharArray();
            char[] chars2 = word2.toCharArray();
            return helper(chars1, chars2, 0, 0);
        }
        
        int helper(char[] chars1, char[] chars2, int idx1, int idx2) {
            if(dp[idx1][idx2] == -1) {
                if(idx1 == chars1.length) {
                    // no more chars for chars1
                    dp[idx1][idx2] = chars2.length - idx2;
                } else if(idx2 == chars2.length) {
                    // no more chars for chars2
                    dp[idx1][idx2] = chars1.length - idx1;
                } else {
                    char char1 = chars1[idx1];
                    char char2 = chars2[idx2];
                    if (char1 == char2) {
                    	// the same as remove char1 and char2
                        dp[idx1][idx2] = helper(chars1, chars2, idx1 + 1, idx2 + 1);
                    } else {
                        // 3 choices: remove char1 and char2, only remove char1, only remove char2
                        dp[idx1][idx2] = Math.min(2 + helper(chars1, chars2, idx1 + 1, idx2 + 1), 1 + helper(chars1, chars2, idx1 + 1, idx2));
                        dp[idx1][idx2] = Math.min(dp[idx1][idx2], 1 + helper(chars1, chars2, idx1, idx2 + 1));
                    }
                }
            }
            return dp[idx1][idx2];
        }
    }
    

Log in to reply
 

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