दूरी संपादित करें - ज्ञापन के साथ

Question

मैं संपादन दूरी की समस्या को करने की कोशिश कर रहा हूं, लेकिन परिणामों को कैश करता हूं इसलिए मैं कॉल दोहराता नहीं हूं। मैप में सबप्रोबल्म्स स्टोर करने की कोशिश करने से पहले यह काम करता था, लेकिन अब यह काम करना बंद कर देता है। कॉल के लिए, "आप नहीं" और "आपको नहीं करना चाहिए" की तुलना करना, यह 1 लौटाता है। जाहिर है, लेकिन क्यों?

using namespace std; 
int counter = 0; 

int match(char c1, char c2){ 
    c1 == c2 ? 0 : 1; 
} 

int edit_distance(string s1, string s2,map<pair<string,string>, int>& memo){ 
    if(memo[make_pair(s1,s2)]) 
    return memo[make_pair(s1,s2)]; 
    int i = s1.size(); 
    int j = s2.size(); 

    if(s1.empty()) 
    return memo[make_pair(s1,s2)] = 1 + j; 
    if(s2.empty()) 
    return memo[make_pair(s1,s2)] = 1 + i; 

    int opt[3]; 

    opt[0] = edit_distance(s1.substr(1), s2.substr(1),memo) + match(s1[i-1],s2[j-1]); 
    opt[1] = edit_distance(s1.substr(1), s2,memo) + 1; 
    opt[2] = edit_distance(s1, s2.substr(1),memo) + 1; 

    int min = opt[0]; 
    for(int i = 1; i < 3; i++){ 
    if(opt[i] < min) 
     min = opt[i]; 
    } 
    memo[ make_pair(s1,s2) ] = min; 
    return min; 
} 

int edit_distance_driver(string s1, string s2){ 
    map<pair<string,string>,int> memo; 
    return edit_distance(s1, s2, memo); 
} 

int main(){ 
    cout << edit_distance_driver("thou shalt not","you should not") << endl; 
} 

Answer 1

समस्या यहाँ है:

opt[0] = edit_distance(s1.substr(1), s2.substr(1),memo) + match(s1[i-1],s2[j-1]); 

आप पहले वर्णों के बिना recurse, लेकिन आप पिछले पात्रों की जाँच करें।

आप के बजाय पहले पात्रों की जांच होनी चाहिए, तो यह होना चाहिए:

opt[0] = edit_distance(s1.substr(1), s2.substr(1),memo) + match(s1[0],s2[0]); 

और स्पष्ट रूप से match कुछ लौटाना चाहिए:

int match(char c1, char c2){ 
    return c1 == c2 ? 0 : 1; 
} 

फिर your code prints 6 for those strings।