Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Solution: The Edit Distance Problem

Learn how to solve the Edit Distance problem with dynamic programming approaches in C#. This lesson guides you through brute force recursion, optimizing with memoization using a lookup table, and finally a bottom-up tabular method. Understand each method's implementation and time complexity to effectively address string similarity challenges in coding interviews.

We'll cover the following...

Solution 1: Brute force

C# 9.0
using System;
class Program
{
    /// <summary>
    /// Calculates the minimum Levenshtein distance between two strings.
    /// </summary>
    /// <param name="str1">First string.</param>
    /// <param name="str2">Second string.</param>
    /// <param name="m">Length of the first string.</param>
    /// <param name="n">Length of the second string.</param>
    /// <returns>The minimum number of Levenshtein distance operations required to transform the first string into the second.</returns>
    public static int MinEditDistRecursive(string str1, string str2, int m, int n)
    {
        // If first string is empty, the only option is to
        // insert all characters of second string into first
        if (m == 0)
            return n;
        // If second string is empty, the only option is to
        // remove all characters of first string
        if (n == 0)
            return m;
        // If last characters of two strings are the same, ignore last characters
        // and get count for remaining strings
        if (str1[m - 1] == str2[n - 1])
            return MinEditDistRecursive(str1, str2, m - 1, n - 1);
        // If last characters are not the same, consider all three operations
        // on the last character of the first string, recursively compute minimum
        // cost for all three operations and take minimum of the three values
        int insertOp = MinEditDistRecursive(str1, str2, m, n - 1);     // Insert
        int removeOp = MinEditDistRecursive(str1, str2, m - 1, n);     // Remove
        int replaceOp = MinEditDistRecursive(str1, str2, m - 1, n - 1); // Replace
        return 1 + Math.Min(Math.Min(insertOp, removeOp), replaceOp);
    }
    /// <summary>
    /// Calculates the minimum Levenshtein distance between two strings.
    /// </summary>
    /// <param name="str1">First string.</param>
    /// <param name="str2">Second string.</param>
    /// <returns>The minimum number of Levenshtein distance operations required to transform the first string into the second.</returns>
    public static int MinEditDist(string str1, string str2)
    {
        return MinEditDistRecursive(str1, str2, str1.Length, str2.Length);
    }
    // Driver code to test the above method
    public static void Main(string[] args)
    {
        string str1 = "sunday";
        string str2 = "saturday";
        Console.WriteLine(MinEditDist(str1, str2));
    }
}

Explanation

We process all the characters of each string, one by one. There are two possibilities for every pair of characters being considered:

  • The end characters of both strings match, in which case, the lengths of both strings are reduced by one, and the function is called recursively on the remaining strings.

  • The end characters of both strings do not match, in which case, all three operations (insertion, deletion, and substitution) are carried out on the last character of the first string.

  • The minimum cost for all three operations is computed recursively and returned.

Time complexity

The time complexity of this code is exponential, i.e., O(3n)O(3^n) ...