Horje
Edit Distance in C++

The Edit Distance problem is a common dynamic programming problem in which we need to transform one string into another with the minimum number of operations. In this article, we will learn how to solve this problem in C++ for two given strings, str1 and str2, and find the minimum number of edits required to convert str1 into str2 by performing the following operations on it:

  • INSERT: Insert a character.
  • REMOVE: Remove a character.
  • REPLACE: Replace a character.

Example:

Input:
str1 = "GEEXSFRGEEKKS"
str2 = "GEEKSFORGEEKS"

Output:
3

Explanation: 
To convert str1 into str2, the minimum operations required are:
Replace ‘X’ with ‘K’.
Insert ‘O’ between ‘F’ and ‘R’.
Remove the second last character ‘K’.
Edit-Distance-Illustration-(1)-copy

Edit Distance in C++

Approaches to Solve Edit Distance in C++ Language

Method 1: Recursive Approach

In recursive approach, we compare characters from the end of both strings and perform operations accordingly. If characters match, we move to the next pair. If they don’t, we consider three operations (insert, remove, replace) and choose the one with the minimum cost.

Approach:

  • If one string is empty, the cost is the length of the other string.
  • If the last characters of both strings match, move to the next pair.
  • If the last characters do not match, consider three operations:
    • Insert: Calculate the cost for str1 and the rest of str2.
    • Remove: Calculate the cost for str2 and the rest of str1.
    • Replace: Calculate the cost for the rest of both strings.
  • Return the minimum of the three operations.

Below is the recursive tree for above approach:

Recursion-Tree-for-Edit-Distance-(1)

C++ Program to Solve Edit Distance Using Recursion

The below program demonstrates how we can solve edit distance problem using recursive approach in C++.

C++ 
// C++ program to calculate the minimum edit distance
// between two strings using recursion

#include <cstring>
#include <iostream>
using namespace std;

int min(int a, int b, int c) { return min(min(a, b), c); }

// Recursive function to find the edit distance
int editDistanceRecursive(string str1, string str2, int m,
                          int n)
{
    // If str1 is empty, insert all characters of str2
    if (m == 0)
        return n;
    // If str2 is empty, remove all characters of str1
    if (n == 0)
        return m;

    // If the last characters match, move to the next pair
    if (str1[m - 1] == str2[n - 1])
        return editDistanceRecursive(str1, str2, m - 1,
                                     n - 1);

    // If the last characters don't match, consider all
    // three operations
    return 1
           + min(editDistanceRecursive(str1, str2, m,
                                       n - 1), // Insert
                 editDistanceRecursive(str1, str2, m - 1,
                                       n), // Remove
                 editDistanceRecursive(str1, str2, m - 1,
                                       n - 1) // Replace
           );
}

int main()
{
    // Initialize two strings
    string str1 = "GEEXSFRGEEKKS";
    string str2 = "GEEKSFORGEEKS";
    // print the minimum edit distance
    cout << "Minimum edit distance is "
         << editDistanceRecursive(str1, str2, str1.length(),
                                  str2.length())
         << endl;
    return 0;
}

Output
Minimum edit distance is 3

Time Complexity: O(3^m), when length of “str1” >= length of “str2” and O(3^n), when length of “str2” > length of “str1”. Here m=length of “str1 and n=length of “str2”
Auxiliary Space: O(m), when length of “str1” >= length of “str2” and O(n), when length of “str2” > length of “str1”. Here m=length of “str1 and n=length of “str2”

Method 2: Dynamic Programming (Memoization)

To optimize the above recursive approach, we store the results of subproblems in a 2D array dp to avoid redundant calculations. This technique is called memoization.

Approach:

  • Create a 2D array dp of size (m+1) x (n+1).
  • Initialize the base cases:
    • If i is 0, fill dp[i][j] with j.
    • If j is 0, fill dp[i][j] with i.
  • Fill the array based on whether the characters match or not:
    • If characters match, copy the diagonal value.
    • If characters don’t match, consider the minimum of insert, remove, and replace operations.
Overlapping-subproblems-in-the-Edit-Distance

C++ Program to Solve Edit Distance Using Dynamic Programming (Memoization)

The below program demonstrates how we can solve edit distance problem using Dynamic Programming (Memoization) in C++.

C++ 
// C++ program to calculate minimum edit distance using
// dynamic programming
#include <iostream>
#include <vector>
using namespace std;

// Helper function to find the minimum of three values
int min(int a, int b, int c)
{
    // Find the smallest value among a, b, and c
    return min(min(a, b), c);
}

// Function to find the edit distance using dynamic
// programming (memoization)
int editDistanceDP(string str1, string str2, int m, int n)
{
    // Create a 2D vector to store the edit distance values
    vector<vector<int> > dp(m + 1, vector<int>(n + 1));

    // Initialize base cases
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            // If str1 is empty, insert all characters of
            // str2
            if (i == 0)
                dp[i][j] = j;
            // If str2 is empty, remove all characters of
            // str1
            else if (j == 0)
                dp[i][j] = i;
            // No new operation needed if last characters
            // match
            else if (str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];

            else
                dp[i][j]
                    = 1
                      + min(
                          dp[i][j - 1], // Insert operation
                          dp[i - 1][j], // Remove operation
                          dp[i - 1]
                            [j - 1] // Replace operation
                      );
        }
    }

    // Return the final edit distance
    return dp[m][n];
}

int main()
{
    // Define input strings
    string str1 = "GEEXSFRGEEKKS";
    string str2 = "GEEKSFORGEEKS";

    // Calculate and output the minimum edit distance
    cout << "Minimum edit distance is "
         << editDistanceDP(str1, str2, str1.length(),
                           str2.length())
         << endl;

    return 0;
}

Output
Minimum edit distance is 3

Time Complexity: O(m x n) 
Auxiliary Space: O( m *n)+O(m+n) , (m*n) extra array space and (m+n) recursive stack space.

Method 3: Dynamic Programming (Bottom-Up)

The bottom-up approach fills the DP table iteratively. This avoids the overhead of recursive calls and makes the process more efficient.

Approach:

  • Create a 2D array dp of size (m+1) x (n+1).
  • Initialize the base cases:
    • If i is 0, fill dp[i][j] with j.
    • If j is 0, fill dp[i][j] with i.
  • Iterate over each character of both strings:
    • If characters match, copy the diagonal value.
    • If characters don’t match, take the minimum of insert, remove, and replace operations.

C++ Program to Solve Edit Distance Using Dynamic Programming (Bottom-Up)

The below program demonstrates how we can solve edit distance problem using Dynamic Programming (Bottom-Up) in C++.

C++ 
// C++ program to calculate minimum edit distance using
// bottom-up dynamic programming

#include <iostream>
#include <vector>
using namespace std;

// Helper function to find the minimum of three values
int min(int a, int b, int c)
{
    // Return the smallest value among a, b, and c
    return min(min(a, b), c);
}

// Function to find the edit distance using bottom-up
// dynamic programming
int editDistanceBottomUp(string str1, string str2)
{
    // Length of the first string
    int m = str1.length();
    // Length of the second string
    int n = str2.length();

    // Create a 2D vector to store the edit distance values
    vector<vector<int> > dp(m + 1, vector<int>(n + 1));

    // Initialize base cases
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            // If str1 is empty, insert all characters of
            // str2
            if (i == 0)
                dp[i][j] = j;
            // If str2 is empty, remove all characters of
            // str1
            else if (j == 0)
                dp[i][j] = i;
            // If last characters match, no new operation
            // needed
            else if (str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else {
                // Consider all three operations: insert,
                // remove, replace
                dp[i][j]
                    = 1
                      + min(
                          dp[i][j - 1], // Insert operation
                          dp[i - 1][j], // Remove operation
                          dp[i - 1]
                            [j - 1] // Replace operation
                      );
            }
        }
    }

    // Return the final edit distance
    return dp[m][n];
}

int main()
{
    // Define input strings
    string str1 = "GEEXSFRGEEKKS";
    string str2 = "GEEKSFORGEEKS";

    // Calculate and output the minimum edit distance
    cout << "Minimum edit distance is "
         << editDistanceBottomUp(str1, str2) << endl;

    return 0;
}

Output
Minimum edit distance is 3

Time Complexity: O(m x n) 
Auxiliary Space: O(m x n)

Method 4: Dynamic Programming (Space-Optimized)

To further optimize space, we use only two arrays to store the current and previous rows of the DP table. This reduces the space complexity to O(n).

Approach:

  • Create two arrays prev and curr of size (n+1).
  • Initialize the prev array for the base case.
  • Iterate over each character of both strings:
    • If characters match, copy the diagonal value.
    • If characters don’t match, take the minimum of insert, remove, and replace operations.
  • Swap the prev and curr arrays after processing each row.

C++ Program to Solve Edit Distance Using Dynamic Programming (Space-Optimized)

The below program demonstrates how we can solve edit distance problem using Dynamic Programming (Space-Optimized) in C++.

C++ 
// C++ program to calculate minimum edit distance using
// space-optimized dynamic programming

#include <iostream>
#include <vector>
using namespace std;

// Helper function to find the minimum of three values
int min(int a, int b, int c)
{
    // Return the smallest value among a, b, and c
    return min(min(a, b), c);
}

// Function to find the edit distance using space-optimized
// dynamic programming
int editDistanceSpaceOptimized(string str1, string str2)
{
    // Length of the first string
    int m = str1.length();
    // Length of the second string
    int n = str2.length();

    // Create two vectors to store the current and previous
    // rows of the DP table
    vector<int> prev(n + 1), curr(n + 1);

    // Initialize the prev vector with base case values
    for (int j = 0; j <= n; j++) {
        // Edit distance when str1 is empty
        prev[j] = j;
    }

    // Iterate over each character of str1
    for (int i = 1; i <= m; i++) {
        // Initialize the first element of curr
        curr[0] = i;

        // Compute edit distance for each substring of str2
        for (int j = 1; j <= n; j++) {
            // If characters match, no new operation needed
            if (str1[i - 1] == str2[j - 1]) {
                curr[j] = prev[j - 1];
            }
            else {
                // Consider all three operations: insert,
                // remove, replace
                curr[j] = 1
                          + min(prev[j], curr[j - 1],
                                prev[j - 1]);
            }
        }

        // Move to the next row by swapping prev and curr
        prev = curr;
    }

    // Return the minimum edit distance
    return prev[n];
}

int main()
{
    // Define input strings
    string str1 = "GEEXSFRGEEKKS";
    string str2 = "GEEKSFORGEEKS";

    // Calculate and output the minimum edit distance
    cout << "Minimum edit distance is "
         << editDistanceSpaceOptimized(str1, str2) << endl;

    return 0;
}

Output
Minimum edit distance is 3

Time Complexity: O(M x N) where M and N are lengths of the string 
Auxiliary Space: O( N ), Length of the str2


 


Reffered: https://www.geeksforgeeks.org

C++

Related
Why Can&#039;t We Declare a std::vector&lt;AbstractClass&gt; in C++? Why Can&#039;t We Declare a std::vector&lt;AbstractClass&gt; in C++?
What Requirements Must std::map Key Classes Meet to be Valid Keys? What Requirements Must std::map Key Classes Meet to be Valid Keys?
C++ 03 Standard C++ 03 Standard
Toggling Bits in C++ Toggling Bits in C++
Alternative to vector&lt;bool&gt; Alternative to vector&lt;bool&gt;

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 20



 

Horje