motatoes's blog

Levenshtein distance Hackerrank problem help
By motatoes, history, 6 years ago, In English

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

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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); }

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you send a link to the source problem?

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply