Naive recursive implementation of edit distance problem.

Recusive Edit Distance.cpp

/*
	Program Name - Edit Distance
	Author Name - Abhey Rana
	Date - 6 December 2017
*/

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

int len1,len2;

int solveEditDistance(string str1, string str2, int i, int j){

	// If str1 == "" then all we can do is insertion .........
	if(i == len1)
		return len2 - j;

	// If str2 == "" then all we can do is deletion .........
	if(j == len2)
		return len1 - i;

	// Two end characters are same hence, there is no need for substitution, insertion or deletion.
	if(str1[i] == str2[j])
		return solveEditDistance(str1,str2,i + 1,j + 1);

	else{

		// Time we choose between substitution, insertion and deletion ..........
		int substitutionCost = 1 + solveEditDistance(str1,str2,i + 1,j + 1);
		int insertionCost = 1 + solveEditDistance(str1,str2,i,j + 1);
		int deletionCost = 1 + solveEditDistance(str1,str2,i + 1,j);

		return min(substitutionCost,min(insertionCost,deletionCost));

	}

}

int main(){

	string str1, str2;
	cin >> str1 >> str2;

	len1 = str1.size();
	len2 = str2.size();

	cout << solveEditDistance(str1,str2,0,0) << endl;

}