編輯距離 - 隨着記憶

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]); 

你遞歸沒有第一字符，但你檢查最後字符。

而應該檢查的第一個字符，所以它應該是：

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。