WA - Edit distance (EDIST - SPOJ)

help
, , ,
1

Am i missing any corner case or anything?

Code: Coding Blocks IDE
Spoj: SPOJ.com - Problem EDIST

This case fails: (from GFG)
Input:
57 44
zvfrkmlnozjkpqpxrjxkitzyxacbhhkicqcoendtomfgdwdwfcgpxiqvk uytdlcgdewhtaciohordtqkvwcsgspqoqmsboaguwnny

Its Correct output is:
50

And Your Code’s output is:
49

2

When a[i] == b[j] you don’t consider anything else.

if( a[i] == b[j] ) { dp[i][j] = dp[i-1][j-1] ; }
else{
dp[i][j] = min( dp[i-1][j-1], dp[i-1][j], dp[i][j-1] ) + 1
}

I got 50 as the answer on the test above once I fixed that.

1 Like
3

Thanks! It worked! Why should i consider them? Shouldn’t we minimize even if we have to delete, remove or insert a character even if it’s a duplicate?

4

Because of the definition of DP.

DP[i][j] = minimum moves required to make a[1…i] == b[1…j] and the operations are possible only at the last indices ( i and j ).
Hence if a[i] == b[j] we don’t have to do anything to make them equal.

DP[i-1][j-1] already gives the minimum moves to make a[1…i-1] == b[1…j-1] and if a[i] == b[j] then obviously DP[i][j] = DP[i-1][j-1]

1 Like