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

maybe

`if (i == 0 or j == 0 ) {`

`// cout << " I was here" << i << " " << j << " " << endl;`

`return max(i,j);`

`}`

change to

`if (i == 0 or j == 0 ) {`

`// cout << " I was here" << i << " " << j << " " << endl;`

`return max(i+1,j+1);`

`}`

Can you send a link to the source problem?

so that we know the input and output format of the problem

Oh sorry, I forgot to link it in the post https://www.hackerrank.com/contests/cse-830-homework-3/challenges/edit-distance/problem

ok i think the problem is that your base case is wrong.

lets suppose we are comparing "a" and "b"

your dp state is (0,0) which your program will return 0.

the thing is we can only have the base case when one of the strings is empty, when i==-1 or j==-1.

Then for the example dp(0,0) will call dp(-1,0).

so this

`if (i == 0 or j == 0 ) {`

`// cout << " I was here" << i << " " << j << " " << endl;`

`return max(i,j);`

`}`

should be change to this

`if (i == -1 or j == -1 ) {`

`// cout << " I was here" << i << " " << j << " " << endl;`

`return max(i,j)+1;`

`}`

I added the +1 because there was a off by 1 for some reason

Thank you! That was the problem. Submission works now but gets TLE for one of the test cases (length of str > 1100)

anyway to make it more efficient ?

You are copying strings with every call of recursive function, therefore getting $$$\mathcal{O}(n^3)$$$ complexity. Changing

`string a, string b`

to`string& a, string& b`

should help.Thanks! Finally got AC

Auto comment: topic has been updated by motatoes (previous revision, new revision, compare).Auto comment: topic has been updated by motatoes (previous revision, new revision, compare).import java.util.Scanner; public class MED {

}