2013-10-25 4 views
5

Я пытаюсь сделать проблему с расстоянием редактирования, но кэширую результаты, чтобы не повторять вызовы. Он работал до того, как я попытался сохранить подзадачи на карте, но теперь он перестает работать. Для звонка, который я делаю, сравнивая «ты не должен» и «не должен», он возвращает 1. Очевидно неправильно, но почему?Редактировать расстояние - с memoization

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; 
} 
+1

Где возвращение в вашем матче? Должна ли быть возвращена c1 == c2? 0: 1; –

ответ

4

Проблемы здесь:

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.

Смежные вопросы