share my easy java dp solution!


  • 0
    T
    public class Solution {
        public int minDistance(String word1, String word2) {
            if(word1==null || word2==null) return 0;
            
            if(word1.length()==0){
                return word2.length();
            }else if(word2.length()==0){
                return word1.length();
            }
            
            char[] array1=word1.toCharArray();
            char[] array2=word2.toCharArray();
            
            Integer[][] dp=new Integer[array1.length][array2.length];
            LargestCommonSub(dp,array1,array2,array1.length-1,array2.length-1);
            return array1.length+array2.length-dp[array1.length-1][array2.length-1]*2;
        }
        
        public int LargestCommonSub(Integer[][] dp,char[] array1,char[] array2,int index1,int index2){
            if(index1<0 || index2<0){
                return 0;
            }else if(dp[index1][index2]!=null){
                return dp[index1][index2];
            }
            
            
            if(array1[index1]==array2[index2]){
             dp[index1][index2]=1+LargestCommonSub(dp,array1,array2,index1-1,index2-1);    
            }else{
             dp[index1][index2]=Math.max(LargestCommonSub(dp,array1,array2,index1-1,index2),LargestCommonSub(dp,array1,array2,index1,index2-1));
            }
            
            return dp[index1][index2];
        }
    }
    
    

Log in to reply
 

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