fork(2) download
copy 
  1. #include<iostream>
  2. #include<string.h>
  3. #define m 20
  4. int arr[m][m];
  5. using namespace std;
  6. int min(int a,int b)
  7. {
  8. 	return a>b?b:a;
  9. }
  10. int min(int a,int b,int c)
  11. {
  12. 	return min(min(a,b),c);
  13. }
  14. int fun(char st1[],char st2[],int low1,int low2,int high1,int high2)
  15. {
  16. 	if(arr[low1][low2]!=-1)
  17. 	   return arr[low1][low2];
  18.     if(low1>high1)
  19.         return (high2-low2+1);
  20.     if(low2>high2)
  21.         return (high1-low1+1);
  22.     arr[low1+1][low2]=fun(st1,st2,low1+1,low2,high1,high2);
  23.     arr[low1][low2+1]=fun(st1,st2,low1,low2+1,high1,high2);
  24.     arr[low1+1][low2+1]=fun(st1,st2,low1+1,low2+1,high1,high2);
  25.     if(st1[low1]!=st2[low2])
  26.        arr[low1][low2]=min(1+arr[low1+1][low2],1+arr[low1][low2+1],1+arr[low1+1][low2+1]);
  27.     else
  28.        arr[low1][low2]=min(1+arr[low1+1][low2],1+arr[low1][low2+1],arr[low1+1][low2+1]);
  29.     return arr[low1][low2];
  30. }
  31. int main()
  32. {
  33.   char st1[] = "sunday" ;
  34.   char st2[] =  "saturday" ;
  35. 	for(int i=0;i<m;i++)
  36. 	{
  37. 		for(int j=0;j<m;j++)
  38. 		{
  39. 			arr[i][j]=-1;
  40. 		}
  41. 	}
  42. 	cout<<fun(st1,st2,0,0,strlen(st1)-1,strlen(st2)-1)<<" is minimum possible changes to convert s1 to s2.\n";
  43. 	return 0;
  44. }
Success #stdin #stdout 0s 3296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3 is minimum possible changes to convert s1 to s2.
https://ideone.com/XAUoU9
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!