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 :)