Levenshtein distance Hackerrank problem help

Revision en3, by motatoes, 2019-05-28 02:01:19

Hello Codeforces,

I'm trying to solve this problem on Hackerrank which is to implement Levenshtein distance. I've written this code which as far as I can tell is correct:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1000;
int memo[N][N];

int lev_dist(string a, string b, int i, int j) {
    if (i == 0 or j == 0 ) {
        // cout << " I was here" << i << " " << j << " " << endl;
        return max(i,j);
    }   
    else {
        
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        else {
            int d1 = lev_dist(a,b,i-1,j)+1;
            int d2 = lev_dist(a,b,i,j-1)+1;
            int d3 = lev_dist(a,b,i-1,j-1);
            // indicator function
            if (a[i] != b[j]) {
                d3 += 1;
            }
            int res = min(d1, min(d2, d3));
            memo[i][j] = res;
            return res;
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        for (int i=0; i<N; i++)
            for (int j=0; j<N; j++)
                memo[i][j] = -1;
        
        string a,b;
        cin >> a;
        cin >> b;
        // cout << "a" << a.length() << "b" << b.length() << endl;
        cout << lev_dist(a,b, a.length()-1, b.length()-1) << endl;
    }
    return 0;
}

However, it fails on the pretests:

INPUT
100
CGICNWFJZOWBDEVORLYOOUHSIPOICMSOQIUBGSDIROYOMJJSLUPVRBNOOPAHMPNGQXHCPSLEYZEYSDGF
TBYHUADAJRXTDDKWMPYKNQFMGBOXJGNLOGIKTLKVUKREEEVZMTCJVUZSHNRZKGRQOXMBZYGBNDFHDVLM
NTBFKWGUYSLYRMMPSXNYXAZNZFJIPJDMNPZNLPEEYEONABFCZEZYVGCJBFMGWKQPTTGJDLKKQYJZYFSL
PEDWJMTVXVGGCLSTOOQEACZJNOVUYXPQGIRAPHFWAESSZKHKGKUEEGVWZXVFJWLQBUBOJMHLEHGKWYTN
RPXZTOSEPHWYBYSOOAKMOOJRSSFHENHDVHOIKVNXMFAEXXTBNPNFPTFGNUPLKDWRSUQYWAUVMNVYJZQL
MFKSTCDHEPTSMYNDRSNJZOULCCIUXZDCGQZRSRYEODXKNBGBBKSPPCQHJYUSCKMJZBPUBLLXPRCQJYRV
USJZEXTQXQYCXPMSRNGIWRHJFQZFQYSOTBEUZMWWHJBOTOUPGLMRDITCGYIUJXGTBIOAJWYXCHUWFNYP
DKAXVOVHAAWFYDZXJHUUXIGQRIBQGNFHYYIYDZDTDYHGOZPRLQLUOHLKWLCPXKVDGWXYROAHSVEICUYF
GMPOQQULURLAFHPSVGLCGWVTGJZEARVPKRKEWEOONARMPIEMYPUJYTHKQBYDMTPXGDKJTSHOJHWIWXBL
VSXFWFBANKGTNLVHZRJPHLGKMTCLSWCIQONXSGEBZESADLWHYUCFLFEJNBISZMVVLLCANHKLRSONBABF
CFACAXPMVDBVRTXQNNALQJVGTRWFIFHUBGFQEUCYVXPABQBPKZWQVRVYIETXJTUKXIDGRRGPYCAOZNEL
UJSLLVNZRJXMXDKRFZMZNQNLZENYKGAKINKZXVRZGCETREQCNCWABDXLKAEBLXRIRDVHELGADMJDMPJN

PROGRAM OUTPUT
73
69
71
71
73
73

JUDGE EXPECTED OUTPUT
74
70
72
72
74
74

can anyone help me find out what I did wrong in my code? Thanks

UPD finally got AC thanks to the comments, my base case was wrong as pointed out in the comments. Also I had to pass strings by reference in order to get the final AC as explained in the comments also :)

Tags dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English motatoes 2019-05-28 02:01:19 211
en2 English motatoes 2019-05-27 23:59:30 93 added link
en1 English motatoes 2019-05-27 22:34:29 2662 Initial revision (published)