# Edit Distance Problem (Levenshtein distance) – Dynamic Programming

There are two strings source and destination. The goal of the problem is to convert source to destination by applying minimum edit operations on string str1.

The edit operations are following –

• Insert
• Remove
• Replace

For example:

``````Str1 = “Name”
Str2 = “Namo”``````

We need only one operation to replace char ‘e’ with char ‘o’

#### Using Recursion

``````using System;
namespace MinimumDistance{
class Program
{
static void Main()
{
var result = MinimumDistanceRecursion("Name","Namo",4,4);
Console.WriteLine(\$"Minimum {result} operation required to transform source to destination.");
}

static int MinimumDistanceRecursion(string source, string destination, int sourceLen, int destinationLen)
{
if (destinationLen == 0)
return sourceLen;
if (sourceLen == 0)
return destinationLen;
if (source[sourceLen - 1] == destination[destinationLen - 1])
return MinimumDistanceRecursion(source, destination, sourceLen - 1, destinationLen - 1);
var x = 1 + MinimumDistanceRecursion(source, destination, sourceLen, destinationLen - 1);
var y = 1 + MinimumDistanceRecursion(source, destination, sourceLen - 1, destinationLen);
var z = 1 + MinimumDistanceRecursion(source, destination, sourceLen - 1, destinationLen - 1);
return Math.Min(x, Math.Min(y, z));
}
}

}``````

#### Using Dynamic Programming

``````using System;
namespace MinimumDistance{
class Program
{
static void Main()
{
var result = MinimumDistanceDynamicProgramming("Name", "Namo", 4, 4);
Console.WriteLine(\$"Minimum {result} operation required to transform source to destination.");
}

static int MinimumDistanceDynamicProgramming(string source, string destination, int sourceLen, int destinationLen)
{
var operationArr = new int[sourceLen + 1, destinationLen + 1];
for (var i = 0; i <= sourceLen; i++)
operationArr[i, 0] = i;
for (var j = 0; j <= destinationLen; j++)
operationArr[0, j] = j;
for (var i = 1; i <= sourceLen; i++)
{
for (var j = 1; j <= destinationLen; j++)
{
if (source[i - 1] == destination[j - 1])
{
operationArr[i, j] = operationArr[i - 1, j - 1];
}
else
{
var x = 1 + operationArr[i - 1, j];
var y = 1 + operationArr[i, j - 1];
var z = 1 + operationArr[i - 1, j - 1];
operationArr[i, j] = Math.Min(x, Math.Min(y, z));
}
}
}
return operationArr[sourceLen, destinationLen];
}
}

}``````