My none recursive solution


  • 5
    B

    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];
                        if(word1.charAt(i-1)!=word2.charAt(j-1)) 
                        {
                            rep+=1;
                        }
                        int min = Math.min(del,ins);
                        min = Math.min(min,rep);
                        result[i][j]=min;
                    }
                }
                return result[word1.length()][word2.length()];
            }
        }

  • 1
    Y

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


  • 0
    S

    Thanks for your post. However it would be better to elaborate thoughts first, then ask for improvement. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    R

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


  • 0

  • 0
    Y

    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.