Problem:Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1′ into ‘str2′.
a.Insert
b.Remove
c.Replace
All of the above operations are of cost=1.Both the strings are of lowercase.
Hint: Use DP to solve the problem. This problema also can be solved using LCS. LCS needs to be applied on the string and its reverse string.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <stdio.h> #include <string.h> int _min(int a,int b,int c) { return (a<(b<c?b:c)?a:(b<c?b:c)); } int main() { //code int t,n,i,m,j; int dp[105][105]; char str1[105]; char str2[105]; scanf("%d",&t); while(t--) { scanf("%d",&n); scanf("%d",&m); scanf("%s",str1); scanf("%s",str2); for(i=0;i<=strlen(str1);i++) { for(j=0;j<=strlen(str2);j++) { if(i==0) dp[i][j]=j; else if(j==0) dp[i][j]=i; else if(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]; else if(str1[i-1]!=str2[j-1]) dp[i][j]= 1+ _min(dp[i][j-1],//insert dp[i-1][j-1],//replace dp[i-1][j]);//remove } } printf("%d\n",dp[n][m]); } return 0; } |