Simple Java DP Solution


  • -1
    A
    public class Solution {
        
        static final int MATCH = 0; static final int INSERT=1; static final int DELETE=2; 
        int[][] dp;
        public int minDistance(String word1, String word2) {
            dp = new int[word1.length()+1][word2.length()+1];
            for (int[] row: dp)
                Arrays.fill(row, -1);
            return minDistance(word1,word2, word1.length(), word2.length());
        }
        public int match(char a, char b){
            if(a==b) return 0;
            return 1;
        }
        public int minDistance(String word1, String word2, int i, int j){
            int k;int[] opt = new int[3];int t;
            
            if(i==0) return j;if(j==0) return i;
            
            opt[MATCH] = (dp[i-1][j-1]!=-1?dp[i-1][j-1]:minDistance(word1, word2, i-1, j-1))+match(word1.charAt(i-1), word2.charAt(j-1));
            opt[INSERT] = (dp[i][j-1]!=-1?dp[i][j-1]:minDistance(word1, word2, i, j-1))+1;
            opt[DELETE] = (dp[i-1][j]!=-1?dp[i-1][j]:minDistance(word1, word2, i-1, j))+1;
    
            dp[i][j] = Math.min(opt[MATCH],opt[INSERT]);
            dp[i][j] = Math.min(dp[i][j],opt[DELETE]);
            return dp[i][j];
        }
    }

Log in to reply
 

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