TLE when using recursive method with cache


  • 0
    D

    I use recursive method with a cache, the idea is when calculating dist(i, j), making use of the value:

    • dist(i-1, j)
    • dist(i, j-1)
    • dist(i-1, j-1)

    which I think is O(m*n), but still got TLE, is the judge too strict or my solution is wrong?

      public class Solution {
            public int minDistance(String word1, String word2) {
                HashMap<String, Integer> cache = new HashMap<String, Integer>();
                return rMinDistance(word1, word2, cache);
            }
            
            public int rMinDistance(String word1, String word2, HashMap<String, Integer> cache) {   
                //base case
                if(word1.length() == 0 || word2.length() == 0)
                    return Math.max(word1.length(), word2.length());
                
                String key = word1 + ":" + word2;
                if(cache.containsKey(key))
                    return cache.get(key);
                        
                //word without last character
                String w1WithoutEnd = word1.substring(0, word1.length()-1);
                String w2WithoutEnd = word2.substring(0, word2.length()-1);
                
                //if last char is the same, then dist(i, i) = dist(i-1, j-1)
                if(word1.charAt(word1.length()-1) == word2.charAt(word2.length()-1)){
                    return minDistance(w1WithoutEnd, w2WithoutEnd);
                }
                
                int dist1 = minDistance(word1, w2WithoutEnd) + 1;
                int dist2 = minDistance(w1WithoutEnd, word2) + 1;
                int dist3 = minDistance(w1WithoutEnd, w2WithoutEnd) +1;
                
                int min = Math.min(Math.min(dist1, dist2), dist3);
                cache.put(key, min);
                
                return min;
            }
        }

  • 1
    R

    The recursive method is exponential, for each non matching character you create 3 recursions!
    Is good just to understand the topic, but you should implement it using something better.

    Actually exists an O(n*m) solution where n and m are the sizes of the world.

    That solution involves dynamic programming and also has been formalized into a very useful algorithm: http://en.wikipedia.org/wiki/Levenshtein_distance

    I suggest you to study dynamic programming (also from Wikipedia) because allow you to understand how to drastically reduce performances of many common problems like this where the natural and naive solution is a recursive implementation.

    Not all the problem naturally solved with recursions can be optimized in this way, the game is understanding where should be applied and where have no sense.

    For example a binary search is not exponential because you have at most only one recursion per call.

    Have a lot of fun ;-)


  • 0
    D

    Your Solution is not exponential, but is not O(nm) either. I think you have a wrong choice in the parameters of your memorization method. The thing is that, as you chose string as parameters, then you need to create strings every time you are gonna call the recursive method. So you have an extra O(n+m) for each call, so your solution is more or less O(nm*(n+m)).

    Try to replace yours parameters in rMinDistance to integers and your solution should work.
    Best regards.


  • 0
    D

    I include my solution in python with memorization using integer as parameters.

    oo=float('inf')
    class Solution:
    # @return an integer
    def minDistance(self, word1, word2):
    n,m=len(word1),len(word2)
    sol=[[None]*(m+2) for i in range(n+2)]

        def recurse(x,y):
            if x==0 and y==0:return 0
            if sol[x][y] is None:
                res=oo
                if x==0:res=y
                elif y==0:res=x
                elif word1[x-1]==word2[y-1]:res=min(res,recurse(x-1,y-1))
                else:res=min(res,recurse(x-1,y-1)+1,recurse(x-1,y)+1,recurse(x,y-1)+1)
                sol[x][y]=res
                
            return sol[x][y]
        
        return recurse(n,m)

Log in to reply
 

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