fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int**DP;
  5. int editDistance(string S1,string S2,int n,int m)
  6. {
  7. 	//cout<<"n="<<n<<" m="<<m<<endl;
  8.  
  9. 	if(m==0)
  10. 	{
  11. 		return n;
  12. 	}
  13.  
  14. 	if(n==0)
  15. 	{
  16. 		return m;
  17. 	}
  18.  
  19. 	if(DP[n][m] != -1)
  20. 	{
  21. 		return DP[n][m];
  22. 	}
  23.  
  24. 	if(S1[n-1] == S2[m-1])
  25. 	{
  26. 		DP[n][m] = editDistance(S1,S2,n-1,m-1);
  27. 		return DP[n][m];
  28. 	}
  29.  
  30.  
  31. 	DP[n][m] = 1+min(editDistance(S1,S2,n-1,m),min(editDistance(S1,S2,n-1,m-1),editDistance(S1,S2,n,m-1)));
  32. 	return DP[n][m];
  33. }
  34.  
  35.  
  36. int main() {
  37.  
  38. 	string S1;
  39. 	string S2;
  40.  
  41. 	cin>>S1>>S2;
  42.  
  43. 	int n = S1.length();
  44. 	int m = S2.length();
  45.  
  46. 	DP = new int*[n+1];
  47. 	for(int i=0;i<=n;i++)
  48. 	{
  49. 		DP[i] = new int[m+1];
  50. 		for(int j=0;j<=m;j++)
  51. 		{
  52. 			DP[i][j]=-1;
  53. 		}
  54. 	}
  55.  
  56. 	for(int i=0;i<=n;i++)
  57. 	{
  58. 		for(int j=0;j<=m;j++)
  59. 		{
  60. 			if(i==0)
  61. 			{
  62. 				DP[i][j]=j;
  63. 			}
  64. 			else if(j==0)
  65. 			{
  66. 				DP[i][j]=i;
  67. 			}
  68. 			else if(S1[i-1] == S2[j-1])
  69. 			{
  70. 				DP[i][j] = DP[i-1][j-1];
  71. 			}
  72. 			else
  73. 			{
  74. 				DP[i][j] = 1+min(DP[i-1][j],min(DP[i-1][j-1],DP[i][j-1]));
  75. 			}
  76. 		}
  77. 	}
  78.  
  79. 	cout<<DP[n][m]<<endl;
  80.  
  81.  
  82. 	return 0;
  83. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
LOVE
MOVIE
stdout
copy 
2
https://ideone.com/oYXu4w
LOVE
MOVIE
language:
C++14 (gcc 8.3)
created:
9 hours 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!