My none recursive solution

  • 5

    Hello, I've finish this problem without recursion. Any comment on how i can improve on the code? Thanks.
    Is there a reason why people are doing recursive builds? (Space vs time?)

    public class Solution {
            public int minDistance(String word1, String word2) {
                int [][] result = new int[word1.length()+1][word2.length()+1];
                //set up deletion into null string;
                for(int i=0;i<=word1.length();i++) result[i][0]=i;
                for(int j=0;j<=word2.length();j++) result[0][j]=j;
                for(int i=1;i<=word1.length();i++)
                    for(int j=1;j<=word2.length();j++)
                        int del = result[i-1][j] +1;
                        int ins = result[i][j-1] +1;
                        int rep = result[i-1][j-1];
                        int min = Math.min(del,ins);
                        min = Math.min(min,rep);
                return result[word1.length()][word2.length()];

  • 1

    Any explanation on this? I can't understand what's rule behind.

  • 0

    Thanks for your post. However it would be better to elaborate thoughts first, then ask for improvement. Please read the FAQ ( for more info.

  • 0

    One trivial thing is to check if any string is null, otherwise it may throw exceptions.

  • 0

  • 0

    from the time complexity POV, the better way to do this problem is through top-down recursion, because you don't have to fill all the values in the table

    yours is the bottom-up iteration, in order to get the final result, all the items in the table are calculated

    consider this case, two words are equal(length n), the top-down version only calculate n value(diagonal) in the table, but the bottom-up version has to calculate n^2 values

Log in to reply

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