My top-down (c++) solution is timing out...even with memoizing? haaaaalp!!!


  • 0
    D
    class Solution {
    public:
        //a memoized top-down DP
        int minDistance(string word1, string word2) {
            //edge conditions/basecases
            if (word1.empty())
                return word2.length();
            if (word2.empty())
                return word1.length();
            //dp lookup
            pair<string,string> p = make_pair(word1,word2);
            map<pair<string,string>,int>::iterator it = memo.find(p);
            if (it != memo.end())
                return it->second;
            //recurrence
            int insert_dist  = 1 + (minDistance (word1, word2.substr(1)));
            int del_dist     = 1 + (minDistance (word1.substr(1), word2));
            int replace_dist = (word1[0] == word2[0] ? 0 : 1) + 
                                    (minDistance (word1.substr(1), word2.substr(1)));
            int mindist = (min(min(insert_dist, del_dist),replace_dist));
            
            memo[p] = mindist;
            
            return mindist;
            
        }
    private:
        map<pair<string,string>, int> memo;
    };
    

    i'm timing out on some large inputs .. but either way...shouldn't be timing out. any ideas here? i can't use unordered_map with std::pair right out of the box so i went with this. am i not memoizing appropriately? should i have a lookup for each : insert_dist, del_dist, and replace_dist? where it bottoms out before the function call or after seems negligible.

    thanks.


  • 0
    N

    You can try my following concise solution(top down memoized). It gets accepted but still is very slow for C++ solution:

    class Solution {
    public:
        int minDistRecur(string s1,string s2,int i,int j,vector<vector<int> >&memo){
            if(i==-1)
                return j+1;
            if(j==-1)
                return i+1;
            if(memo[i][j]!=-1)  
                return memo[i][j];
            memo[i][j]=min((s1[i]!=s2[j])+minDistRecur(s1,s2,i-1,j-1,memo),min(1+minDistRecur(s1,s2,i-1,j,memo),1+minDistRecur(s1,s2,i,j-1,memo)));
            return memo[i][j];
        }
        int minDistance(string word1, string word2) {
            vector<vector<int> >memo(word1.length(), vector<int>(word2.length(),-1));
            return minDistRecur(word1,word2,word1.length()-1,word2.length()-1,memo);
        }
    };

Log in to reply
 

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