Most Space efficient & O(nm) Time


  • 0
    A
    public int minDistance(String s1, String s2) {
            if(s2.length()<s1.length()) return minDistance(s2, s1);
            int temp,temp2 =0;
            int dp[] = new int[s1.length()+1];
            for(int i=0;i<=s1.length();i++)
                dp[i] =i;
       
            for(int j=1;j<=s2.length();j++){
                temp = dp[0]++;
                for(int i=1;i<=s1.length();i++){
                    temp2 = dp[i];
                    dp[i] = s1.charAt(i-1)==s2.charAt(j-1) ? temp: Math.min(dp[i-1],dp[i])+1;
                    temp = temp2;
                }
            }
            return dp[s1.length()];
        }

Log in to reply
 

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