Hello Codeforces,↵
↵
I'm trying to solve [this problem on Hackerrank](https://www.hackerrank.com/contests/cse-830-homework-3/challenges/edit-distance/problem) 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 :)
↵
I'm trying to solve [this problem on Hackerrank](https://www.hackerrank.com/contests/cse-830-homework-3/challenges/edit-distance/problem) 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 :)
