Algorithms for Coding Interviews in Java/

...

/

Solution: The Edit Distance Problem

Solution: The Edit Distance Problem

This review provides a detailed analysis of three different ways to solve the famous edit distance problem.

We'll cover the following...

Solution #1: Brute force

Let’s start by looking at the brute force solution to solve this problem first:

Java
class EditDistance
{ 
  //Function to find the minimum of three integers 
  public static int min(int a,int b,int c) 
  { 
    if (a <= b && a <= c) return a; 
    if (b <= a && b <= c) return b; 
    else return c; 
  } 
  public static int minEditDistance(String str1, String str2, int m, int n) 
  {
    if (m == 0) return n; // In case the first string is empty, insert all characters of the second string into first to make them similar
    if (n == 0) return m; //  In case the second string is empty, remove all the characters of the first string to make it simialar to the secong string
    if (str1.charAt(m - 1) == str2.charAt(n - 1)) // In case last characters are same, ignore the last char and count for the remaining string 
      return minEditDistance(str1, str2, m - 1, n - 1);
    // In case last characters are not same, consider all three operations on last character of first String, recursively 
    // compute minimum cost for all three operations and take minimum of three values. 
    return 1 + min(minEditDistance(str1, str2, m, n - 1), // Insertion 
      minEditDistance(str1, str2, m - 1, n),              // Deletion 
      minEditDistance(str1, str2, m - 1, n - 1)           // Substitution 
    );
  }
  public static void main(String args[]) 
  {
    String str1 = "Tuesday";
    String str2 = "Thursday";
    System.out.println("Edit Distance of " + str1 + ", " + str2 + " = " + minEditDistance(str1, str2, str1.length(), str2.length()));
  }
}

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 the strings match. In which case, the lengths of both the strings are reduced by one and the function is called recursively on the remaining strings (lines 17-18).

  • The end characters of both the 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 (lines 22-24).

  • The minimum cost for all three operations is computed recursively and returned (lines 22-24).

Time complexity

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