### motatoes's blog

By motatoes, history, 3 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 :)  Comments (10)
 » 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); }
 » 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
•  » » » 3 years ago, # ^ | ← Rev. 3 →   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
•  » » » » 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 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); sc.nextLine(); for (int i = 0; i < t; i++) { String s1 =sc.nextLine(); String s2 = sc.nextLine(); System.out.println(minimumEditDistance(s1,s2)); } } private static int minimumEditDistance(String s1,String s2) { int[][] dp = new int[s1.length()+1][s2.length()+1]; for (int i = 0; i < s1.length(); i++) { dp[i] = i; } for (int i = 0; i < s2.length(); i++) { dp[i] = i; } for (int i = 1; i <= s1.length(); i++) { for (int j = 1; j <= s2.length(); j++) { if(s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1; } } return dp[s1.length()][s2.length()]; } private static int min(int a,int b,int c) { int min = Math.min(a, b); return Math.min(min, c); }}