Edit Distance in C++

Suppose we have two words word1 and word2, we have to find the minimum number of operations required to concert from word1 to word2. The operations can be of three types, these are insert a character, delete a character and replace a character. So if the input strings are “evaluate” and “fluctuate”, then the result will be 5.

To solve this, we will follow these steps −

• n := size of w1, m := size of w2,

• create an array dp of size n + 1

• for i in range 0 to n

  • dp[i] := new array of size m + 1

  • for j in range 0 to m −

    • dp[i, j] := 0

    • if i = 0, then dp[i,j] = j

    • otherwise when j = 0, then dp[i, j] := i

• w1 := blank space and concatenate w1, w2 := blank space and concatenate w2

• for i in range 1 to n

  • for j in range 1 to m

    • if w1[i] is not w2[j], then dp[i, j] := 1 + min of dp[i – 1, j], dp[i, j - 1], dp[i – 1, j – 1]

    • otherwise dp[i, j] := dp[i – 1, j – 1]

• return dp[n, m]

Example

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minDistance(string w1, string w2) {
      int n = w1.size();
      int m =w2.size();
      int** dp = new int*[n+1];
      for(int i =0;i<=n;i++){
         dp[i] = new int[m+1];
         for(int j=0;j<=m;j++){
            dp[i][j]=0;
            if(i==0)dp[i][j]=j;
            else if(j==0)dp[i][j] = i;
         }
      }
      w1 = " " + w1;
      w2 = " " + w2;
      for(int i =1;i<=n;i++){
         for(int j = 1;j<=m;j++){
            if(w1[i] !=w2[j]){
               dp[i][j] = 1+min({dp[i-1][j],dp[i][j-1],dp[i1][j-1]});
            } else {
               dp[i][j] = dp[i-1][j-1];
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.minDistance("fluctuate", "evaluate"));
}

Input

"fluctuate"
"evaluate"

Output

5