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 :

DP[str1.length][str2.length]

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

Code:

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 :

DP[str1.length][str2.length]

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

Code:

## No comments:

## Post a Comment