Wednesday, January 16, 2019

Minimum String Edit Distance DP Problem

Problem Statement : [SPOJ EDIST]

You are given two strings, A and B. Answer, what is the smallest number of operations you need to
transform A to B?

Operations are:

Delete one letter from one of strings
Insert one letter into one of strings
Replace one of letters from one of strings with another letter

Algorithm :


At each point pair (x, y) (x index in string 1 and y index in string 2), you either have matching values in strings or dont.

If you have matching values, you can proceed to x+1, y+1.

Otherwise, you have 3 choices:

1. Delete 1 letter from first string
2. Insert 1 letter to first string
3. Replace 1 letter to match second string

Each operation adds 1 to the cost of making strings equal.

if (str1[i] == str2[j])
return dp[i][j] = solve(i + 1, j + 1);
else return dp[i][j] = 1 + Math.min(Math.min(solve(i + 1, j), solve(i, j + 1)), solve(i + 1, j + 1));


No comments:

Post a Comment