Normal DP solution in C++ - can you tell me the complexity of my code?


  • 0
    R
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            cache=vector<vector<int>>(word1.size()+1, vector<int>(word2.size()+1,-1));
            return minDistance(word1, 0,  word2, 0);
        }
    private:
        int minDistance(const string& word1, int a, const string& word2, int b) {
            if(a==word1.size() && b==word2.size()) return 0;
            if(a==word1.size()) return word2.size()-b;
            if(b==word2.size()) return word1.size()-a;
            if(cache[a][b]!=-1) return cache[a][b];
            
            if(word1[a]==word2[b]){
                return cache[a][b]=minDistance(word1, a+1, word2, b+1);
            }else{
                return cache[a][b]=min(min(minDistance(word1,a+1,word2,b+1), minDistance(word1,a,word2,b+1)), minDistance(word1,a+1,word2,b))+1; 
            }
        }
        vector<vector<int>> cache;
    };

Log in to reply
 

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