fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Edit Distance
  4. //
  5. //  Created by Himanshu on 16/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <string>
  10. using namespace std;
  11.  
  12. int solve (string s1, string s2) {
  13.     int n = (int) s1.length(), m = (int) s2.length();
  14.     int dp[n+1][m+1];
  15.  
  16.     for (int i=0; i<=n; i++) {
  17.         for (int j=0; j<=m; j++) {
  18.             dp[i][j] = 0;
  19.         }
  20.     }
  21.  
  22.     for (int i=0; i<=n; i++) {
  23.         dp[i][0] = i;
  24.     }
  25.  
  26.     for (int j=0; j<=m; j++) {
  27.         dp[0][j] = j;
  28.     }
  29.  
  30.     for (int i=1; i<=n; i++) {
  31.         for (int j=1; j<=m; j++) {
  32.             if (s1[i-1] == s2[j-1]) {
  33.                 dp[i][j] = dp[i-1][j-1];
  34.             }
  35.             else {
  36.                 dp[i][j] = 1 + min((min(dp[i-1][j], 
  37.                                       dp[i][j-1])), 
  38.                                       dp[i-1][j-1]);
  39.             }
  40.  
  41.         }
  42.     }
  43.  
  44.     return dp[n][m];
  45. }
  46.  
  47. int main() {
  48.     string s1 = "hello", s2 = "tell";
  49.     cout<<solve(s1, s2)<<endl;
  50. }
  51.  
Success #stdin #stdout 0.01s 5676KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/uMhxri
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 years ago
visibility:
secret

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!