Algorithms for Coding Interviews in C++/

...

/

Solution: The Edit Distance Problem

Solution: The Edit Distance Problem

This review provides a detailed analysis of the ways to solve the famous Edit Distance problem.

We'll cover the following...

Solution #1: Brute Force

C++
#include <iostream>
using namespace std;
// Utility function to find minimum of three numbers 
int min(int x, int y, int z) {
  return min(min(x, y), z);
}
int minEditDist(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 same, nothing 
  // much to do. Ignore last characters and get count for 
  // remaining strings. 
  if (str1[m - 1] == str2[n - 1])
    return minEditDist(str1, str2, m - 1, n - 1);
  // If 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(minEditDist(str1, str2, m, n - 1), // Insert 
    minEditDist(str1, str2, m - 1, n), // Remove 
    minEditDist(str1, str2, m - 1, n - 1) // Replace 
  );
}
// Driver program 
int main() {
  // your code goes here 
  string str1 = "sunday";
  string str2 = "saturday";
  cout << minEditDist(str1, str2, str1.length(), str2.length());
  return 0;
}

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

Pseudocode

 IF str1[m-1]==str2[n-1]
   Ignore them and get the count for remaining strings. So we call the function for lengths m-1 and n-1.
ELSE
 we consider all operations on ‘str1’, consider all three operations on the last character of the first string, recursively compute the minimum cost for all three operations and return the minimum of the three values.
  Insert: Call function for m and n-1
  Remove: Call function for m-1 and n
  Replace: Call function for m-1 and n-1

Time Complexity

The time complexity of this code is exponential, i.e. ...