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

  • 0
    class Solution {
        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);
        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];
                return cache[a][b]=minDistance(word1, a+1, word2, b+1);
                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.