Iterative implementation of edit distance problem.

Iterative Edit Distance.cpp

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

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

int solveEditDistance(string str1, string str2){

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


	int dp[len1 + 1][len2 + 1];

	for(int i = len1; i >= 0 ; i --){

		for(int j = len2; j>= 0 ; j --){

			if(i == len1){

				// If str1 == "" then all we can do is insertion .........
				dp[i][j] = len2 - j;

			}

			else if(j == len2){

				// If str2 == "" then all we can do is delete .........
				dp[i][j] = len1 - i;

			}

			else if(str1[i] == str2[j]){

				// Two end characters are same hence, there is no need for substitution, insertion or deletion.
				dp[i][j] = dp[i + 1][j + 1];

			}

			else{

				// Time we choose between substitution, insertion and deletion ..........
				// We directly jump to dp[i + 1][j + 1] in case of substitution.
				// We jump to dp[i + 1][j] in case of deletion.
				// We jump to dp[i][j + 1] in case of insertion.
				dp[i][j] = 1 + min(dp[i + 1][j + 1],min(dp[i + 1][j],dp[i][j + 1]));

			}

		}

	}

	return dp[0][0];

}

int main(){

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

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

}