fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int findEditDistance(string s1,string s2,int len1, int len2){
  5. 	int dist[len1+1][len2+1];
  6.  
  7. 	for(int i=0;i<=len1;i++){
  8. 		dist[i][0] = i;
  9. 	}
  10. 	for(int j=0;j<=len2;j++){
  11. 		dist[0][j] = j;
  12. 	}
  13.  
  14. 	for(int i=1;i<=len1;i++){
  15. 		for(int j=1;j<=len2;j++){
  16. 			dist[i][j] = min(((s1[i-1]!=s2[j-1])?1:0) + dist[i-1][j-1],min(1+dist[i-1][j],1+dist[i][j-1]));
  17. 		}
  18. 	}
  19.  
  20. 	for(int i=0;i<=len1;i++){
  21. 		for(int j=0;j<=len2;j++){
  22. 			cout<<dist[i][j]<<" ";
  23. 		}
  24. 		cout<<endl;
  25. 	}
  26.  
  27. 	return dist[len1][len2];
  28. }
  29. int main() {
  30. 	// your code goes here
  31. 	string s1,s2;
  32. 	cin>>s1>>s2;
  33.  
  34. 	int len1 = s1.length();
  35. 	int len2 = s2.length();
  36.  
  37. 	int editDist = findEditDistance(s1,s2,len1,len2);
  38. 	cout<<editDist<<endl;
  39. 	return 0;
  40. }
Success #stdin #stdout 0s 4560KB
comments (?)
stdin
copy 
sitting 
kitten
stdout
copy 
0 1 2 3 4 5 6 
1 2 3 4 5 6 7 
2 3 2 3 4 5 6 
3 4 3 2 3 4 5 
4 5 4 3 2 3 4 
5 6 5 4 3 4 5 
6 7 6 5 4 5 4 
7 8 7 6 5 6 5 
5
https://ideone.com/KqBgj1
language:
C++ (gcc 8.3)
created:
4 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!