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