Midnight Code: learn before you sleep. (Day 2)

EditDistance.cpp

/*
    Given two words Word1 and Word2 find minimum number of operations required to convert Word1 to Word2.
    You have the following 3 operations permitted on a word:
    Insert a character 
    Delete a character
    Replace a character
*/

// minimum of three numbers
int min(int x, int y, int z) 
{ 
    return min(min(x, y), z); 
} 

int EditDistance( string word1, int len1, string word2, int len2 ) {
  
  //base case
  if(len1 == 0)
    return len2;
  if(len2 == 0)
    return len1;
  
  if( word1[len1-1] == word2[len2-1] ){
    return EditDistance( word1, len1-1, word2, len2-1 );
  }
  
  return 1 + min( EditDistance( word1, len1, word2, len2-1 ), // Insert
                  EditDistance( word1, len1-1, word2, len2 ), // Delete
                  EditDistance( word1, len1-1, word2, len2-1) // Replace
                );
  
}

int main(){
  string word1, word2;
  cin >> word1 >> word2;
  cout << EditDistance( word1, word1.length(), word2, word2.length() );
}

EditDistanceDP.cpp

/*

	======================EDIT DISTANCE (DYNAMIC PROGRAMMING SOLUTION)======================

    Given two words Word1 and Word2 find minimum number of operations required to convert Word1 to Word2.
    You have the following 3 operations permitted on a word:
    Insert a character 
    Delete a character
    Replace a character
    
*/

#include<bits/stdc++.h>
using namespace std;

//minimum of three numbers
int min(int x, int y, int z) 
{ 
    return min(min(x, y), z); 
} 

int EditDistance( string word1, int len1, string word2, int len2, int** dp ) {
  
  // if already computed then return the answer directly.
  if( dp[len1][len2] != -1 )
    return dp[len1][len2];
  
  //base cases
  if(len1 == 0)
    return len2;
  if(len2 == 0)
    return len1;
  
  if( word1[len1-1] == word2[len2-1] ){
    dp[len1][len2] = EditDistance( word1, len1-1, word2, len2-1, dp );
    return dp[len1][len2];
  }
  
  dp[len1][len2] =  1 + min( EditDistance( word1, len1, word2, len2-1, dp ), // Insert
                             EditDistance( word1, len1-1, word2, len2, dp ), // Delete
                             EditDistance( word1, len1-1, word2, len2-1, dp) // Replace
                           );
  return dp[len1][len2];
  
}

int main(){
 
  string word1, word2;
  cin >> word1 >> word2;
  int len1 = word1.length();
  int len2 = word2.length();
  
  // making a dp array to store calculated cases.
  int** dp = new int*[len1+1];
  
  // initializing the dp array with -1
  for(int i=0 ; i<=len1 ; i++){
        dp[i] = new int[len2+1];
        for(int j=0 ; j<=len2 ; j++)
            dp[i][j] = -1;
  }
  
  cout << EditDistance( word1, word1.length(), word2, word2.length(), dp );
}