### motatoes's blog

By motatoes, history, 5 years ago,

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
NTBFKWGUYSLYRMMPSXNYXAZNZFJIPJDMNPZNLPEEYEONABFCZEZYVGCJBFMGWKQPTTGJDLKKQYJZYFSL
PEDWJMTVXVGGCLSTOOQEACZJNOVUYXPQGIRAPHFWAESSZKHKGKUEEGVWZXVFJWLQBUBOJMHLEHGKWYTN
MFKSTCDHEPTSMYNDRSNJZOULCCIUXZDCGQZRSRYEODXKNBGBBKSPPCQHJYUSCKMJZBPUBLLXPRCQJYRV
USJZEXTQXQYCXPMSRNGIWRHJFQZFQYSOTBEUZMWWHJBOTOUPGLMRDITCGYIUJXGTBIOAJWYXCHUWFNYP
DKAXVOVHAAWFYDZXJHUUXIGQRIBQGNFHYYIYDZDTDYHGOZPRLQLUOHLKWLCPXKVDGWXYROAHSVEICUYF
GMPOQQULURLAFHPSVGLCGWVTGJZEARVPKRKEWEOONARMPIEMYPUJYTHKQBYDMTPXGDKJTSHOJHWIWXBL
CFACAXPMVDBVRTXQNNALQJVGTRWFIFHUBGFQEUCYVXPABQBPKZWQVRVYIETXJTUKXIDGRRGPYCAOZNEL

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

• 0

| Write comment?
 » 5 years ago, # |   0 maybe if (i == 0 or j == 0 ) { // cout << " I was here" << i << " " << j << " " << endl; return max(i,j); } change toif (i == 0 or j == 0 ) { // cout << " I was here" << i << " " << j << " " << endl; return max(i+1,j+1); }
 » 5 years ago, # |   0 Can you send a link to the source problem?so that we know the input and output format of the problem
•  » » 5 years ago, # ^ |   0 Oh sorry, I forgot to link it in the post https://www.hackerrank.com/contests/cse-830-homework-3/challenges/edit-distance/problem
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 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 thisif (i == 0 or j == 0 ) {// cout << " I was here" << i << " " << j << " " << endl;return max(i,j);} should be change to thisif (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
•  » » » » 5 years ago, # ^ |   0 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 ?
•  » » » » » 5 years ago, # ^ |   0 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.