AlgoDaily - Edit Distance

Home > Dynamic Programming > Dynamic Programming > Edit Distance

Calculating Edit Distance

When it comes to calculating edit distance between two strings, there are several approaches available. One commonly used approach is the dynamic programming algorithm.

The dynamic programming algorithm uses a bottom-up approach to build a matrix that represents the edit distance between substrings of the two input strings. Each cell in the matrix represents the minimum number of operations required to transform one substring into another.

Here's an example of the dynamic programming algorithm in C#:

SNIPPET

1{code}

xxxxxxxxxx
}
 
using System;
​
public class EditDistance
{
    public static int CalculateEditDistance(string str1, string str2)
    {
        int[,] dp = new int[str1.Length + 1, str2.Length + 1];
​
        for (int i = 0; i <= str1.Length; i++)
        {
            for (int j = 0; j <= str2.Length; j++)
            {
                if (i == 0)
                {
                    dp[i, j] = j;
                }
                else if (j == 0)
                {
                    dp[i, j] = i;
                }
                else if (str1[i - 1] == str2[j - 1])
                {
                    dp[i, j] = dp[i - 1, j - 1];
                }
                else
                {
                    dp[i, j] = 1 + Math.Min(Math.Min(dp[i - 1, j], dp[i, j - 1]), dp[i - 1, j - 1]);
                }
            }

Calculating Edit Distance

Programming Categories

Popular Lessons