# WA - Edit distance (EDIST - SPOJ) **URL:** \ **Category:** help\ **Tags:** help, dynamic-programming, easy, wa\ **Created:** [May 30, 2019, 5:26am UTC](https://discuss.codechef.com/t/wa-edit-distance-edist-spoj/26657 "2019-05-30T05:26:38Z")\ **Posts on this page:** 4\ **Page:** 1
**Author:** ![hetp111](https://discuss.codechef.com/user_avatar/discuss.codechef.com/hetp111/32/241932_2.png) [@hetp111](https://discuss.codechef.com/u/hetp111)\ **Post date:** [May 30, 2019, 5:26am UTC](https://discuss.codechef.com/t/wa-edit-distance-edist-spoj/26657/1 "2019-05-30T05:26:39Z")
Am i missing any corner case or anything? Code: [Coding Blocks IDE](https://ide.codingblocks.com/s/75774) Spoj: [SPOJ.com - Problem EDIST](https://www.spoj.com/problems/EDIST/) This case fails: (from GFG) Input: 57 44 zvfrkmlnozjkpqpxrjxkitzyxacbhhkicqcoendtomfgdwdwfcgpxiqvk uytdlcgdewhtaciohordtqkvwcsgspqoqmsboaguwnny Its Correct output is: 50 And Your Code’s output is: 49 ---
**Author:** ![rgkbitw](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rgkbitw/32/3653_2.png) [@rgkbitw](https://discuss.codechef.com/u/rgkbitw)\ **Post date:** [May 30, 2019, 6:49am UTC](https://discuss.codechef.com/t/wa-edit-distance-edist-spoj/26657/2 "2019-05-30T06:49:27Z")
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. ---
**Author:** ![hetp111](https://discuss.codechef.com/user_avatar/discuss.codechef.com/hetp111/32/241932_2.png) [@hetp111](https://discuss.codechef.com/u/hetp111)\ **Post date:** [May 30, 2019, 6:54am UTC](https://discuss.codechef.com/t/wa-edit-distance-edist-spoj/26657/3 "2019-05-30T06:54:42Z")
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? ---
**Author:** ![rgkbitw](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rgkbitw/32/3653_2.png) [@rgkbitw](https://discuss.codechef.com/u/rgkbitw)\ **Post date:** [May 30, 2019, 11:07am UTC](https://discuss.codechef.com/t/wa-edit-distance-edist-spoj/26657/4 "2019-05-30T11:07:20Z")
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]