Home Data Structures and Algorithms Edit Distance Using Dynamic Programming (Optimization in Space Complexity)

Edit Distance Using Dynamic Programming (Optimization in Space Complexity)

Edit Distance Using Dynamic Programming (Bottom-Up Approach):

Edit Distance Using Dynamic Programming (Further Optimization in Space Complexity):

Optimized Space Complexity Solution: In the above bottom up approach we require O(m x n) space. Let’s take an observation and try to optimize our space complexity:

To fill a row in DP array we require only one row i.e. the upper row. For example, if we are filling the row where i=10 in DP array then we require only values of 9th row. So we simply create a DP array of 2 x str1 length. This approach reduces the space complexity from O(N*M) to O(2*N).

Below is the implementation of the above approach:

C++ 
// A Space efficient Dynamic Programming
// based C++ program to find minimum
// number operations to convert str1 to str2
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // space optimization
    int editDistance(string s, string t)
    {
        int m = s.size();
        int n = t.size();

        vector<int> prev(n + 1, 0), curr(n + 1, 0);

        for (int j = 0; j <= n; j++) {
            prev[j] = j;
        }

        for (int i = 1; i <= m; i++) {
            curr[0] = i;
            for (int j = 1; j <= n; j++) {
                if (s[i - 1] == t[j - 1]) {
                    curr[j] = prev[j - 1];
                }
                else {
                    int mn
                        = min(1 + prev[j], 1 + curr[j - 1]);
                    curr[j] = min(mn, 1 + prev[j - 1]);
                }
            }
            prev = curr;
        }

        return prev[n];
    }
};

int main()
{
    string s = "GEEXSFRGEEKKS", t = "w3wiki";

    Solution ob;
    int ans = ob.editDistance(s, t);
    cout << ans << "\n";

    return 0;
}
C 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int min(int a, int b, int c)
{
    if (a < b && a < c) {
        return a;
    }
    else if (b < a && b < c) {
        return b;
    }
    else {
        return c;
    }
}

int editDistance(char* s, char* t)
{
    int n = strlen(s);
    int m = strlen(t);

    int* prev = (int*)calloc(m + 1, sizeof(int));
    int* curr = (int*)calloc(m + 1, sizeof(int));

    for (int j = 0; j <= m; j++) {
        prev[j] = j;
    }

    for (int i = 1; i <= n; i++) {
        curr[0] = i;
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                curr[j] = prev[j - 1];
            }
            else {
                int mn = min(1 + prev[j], 1 + curr[j - 1],
                             1 + prev[j - 1]);
                curr[j] = mn;
            }
        }
        memcpy(prev, curr, (m + 1) * sizeof(int));
    }

    int ans = prev[m];
    free(prev);
    free(curr);

    return ans;
}

int main()
{
    char s[] = "GEEXSFRGEEKKS";
    char t[] = "w3wiki";

    int ans = editDistance(s, t);
    printf("%d\n", ans);

    return 0;
}
Java 
// A Space efficient Dynamic Programming
// based Java  program to find minimum
// number operations to convert str1 to str2
import java.util.*;

class Solution {
    // space optimization
    public int editDistance(String s, String t)
    {
        int n = s.length();
        int m = t.length();

        int[] prev = new int[m + 1];
        int[] curr = new int[m + 1];

        for (int j = 0; j <= m; j++) {
            prev[j] = j;
        }

        for (int i = 1; i <= n; i++) {
            curr[0] = i;
            for (int j = 1; j <= m; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    curr[j] = prev[j - 1];
                }
                else {
                    int mn = Math.min(1 + prev[j],
                                      1 + curr[j - 1]);
                    curr[j] = Math.min(mn, 1 + prev[j - 1]);
                }
            }
            prev = curr.clone();
        }

        return prev[m];
    }
}

public class Main {
    public static void main(String[] args)
    {
        String s = "GEEXSFRGEEKKS";
        String t = "w3wiki";

        Solution ob = new Solution();
        int ans = ob.editDistance(s, t);
        System.out.println(ans);
    }
}
Python3 
# A Space efficient Dynamic Programming
# based Python3 program to find minimum
# number operations to convert str1 to str2


class Solution:
    def editDistance(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

        prev = [j for j in range(m+1)]
        curr = [0] * (m+1)

        for i in range(1, n+1):
            curr[0] = i
            for j in range(1, m+1):
                if s[i-1] == t[j-1]:
                    curr[j] = prev[j-1]
                else:
                    mn = min(1 + prev[j], 1 + curr[j-1])
                    curr[j] = min(mn, 1 + prev[j-1])
            prev = curr.copy()

        return prev[m]


s = "GEEXSFRGEEKKS"
t = "w3wiki"

ob = Solution()
ans = ob.editDistance(s, t)
print(ans)
C# 
using System;
using System.Collections.Generic;

class Solution {
    public int EditDistance(string s, string t)
    {
        int n = s.Length;
        int m = t.Length;

        List<int> prev = new List<int>();
        List<int> curr = new List<int>();

        for (int j = 0; j <= m; j++) {
            prev.Add(j);
        }

        for (int i = 1; i <= n; i++) {
            curr.Add(i);
            for (int j = 1; j <= m; j++) {
                if (s[i - 1] == t[j - 1]) {
                    curr.Add(prev[j - 1]);
                }
                else {
                    int mn = Math.Min(1 + prev[j],
                                      1 + curr[j - 1]);
                    curr.Add(Math.Min(mn, 1 + prev[j - 1]));
                }
            }
            prev = new List<int>(curr);
            curr.Clear();
        }

        return prev[m];
    }
}

class Program {
    static void Main(string[] args)
    {
        string s = "GEEXSFRGEEKKS";
        string t = "w3wiki";

        Solution ob = new Solution();
        int ans = ob.EditDistance(s, t);
        Console.WriteLine(ans);
    }
}
JavaScript 
class Solution {
  // space optimization
  editDistance(s, t) {
    const n = s.length;
    const m = t.length;
 
    const prev = new Array(m + 1).fill(0);
    const curr = new Array(m + 1).fill(0);
 
    for (let j = 0; j <= m; j++) {
      prev[j] = j;
    }
 
    for (let i = 1; i <= n; i++) {
      curr[0] = i;
      for (let j = 1; j <= m; j++) {
        if (s[i - 1] === t[j - 1]) {
          curr[j] = prev[j - 1];
        } else {
          const mn = Math.min(1 + prev[j], 1 + curr[j - 1]);
          curr[j] = Math.min(mn, 1 + prev[j - 1]);
        }
      }
      prev.splice(0, m + 1, ...curr);
    }
 
    return prev[m];
  }
}
 
const s = "GEEXSFRGEEKKS";
const t = "GEEKSFPRGEEKS";
 
const ob = new Solution();
const ans = ob.editDistance(s, t);
console.log(ans);

Output
3

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

Edit Distance

Given two strings str1 and str2 of length M and N respectively and below operations that can be performed on str1. Find the minimum number of edits (operations) to convert ‘str1‘ into ‘str2‘.  

  • Operation 1 (INSERT): Insert any character before or after any index of str1
  • Operation 2 (REMOVE): Remove a character of str1
  • Operation 3 (Replace): Replace a character at any index of str1 with some other character.

Note: All of the above operations are of equal cost. 

Examples: 

Input:   str1 = “geek”, str2 = “gesek”
Output:  1
Explanation: We can convert str1 into str2 by inserting a ‘s’ between two consecutive ‘e’ in str2.

Input:   str1 = “cat”, str2 = “cut”
Output:  1
Explanation: We can convert str1 into str2 by replacing ‘a’ with ‘u’.

Input:   str1 = “sunday”, str2 = “saturday”
Output:  3
Explanation: Last three and first characters are same.  We basically need to convert “un” to “atur”.  This can be done using below three operations. Replace ‘n’ with ‘r’, insert t, insert a

Illustration of Edit Distance:

Let’s suppose we have str1=”GEEXSFRGEEKKS” and str2=”w3wiki”
Now to convert str1 into str2 we would require 3 minimum operations:
Operation 1: Replace ‘X‘ to ‘K‘
Operation 2: Insert ‘O‘ between ‘F‘ and ‘R‘
Operation 3: Remove second last character i.e. ‘K‘

Refer the below image for better understanding.

Recommended Practice
Edit Distance
Try It!

Similar Reads

Edit Distance using Recursion:

Subproblems in Edit Distance:...

Edit Distance Using Dynamic Programming (Memoization):

In the above recursive approach, there are several overlapping subproblems:Edit_Distance(M-1, N-1) is called Three times Edit_Distance(M-1, N-2) is called Two times Edit_Distance(M-2, N-1) is called Two times. And so on… So, we can use Memoization technique to store the result of each subproblems to avoid recalculating the result again and again. Below are the illustration of overlapping subproblems during the recursion....

Edit Distance Using Dynamic Programming (Bottom-Up Approach):

Use a table to store solutions of subproblems to avoiding recalculate the same subproblems multiple times. By doing this, if same subproblems repeated during, we retrieve the solutions from the table itself....

Edit Distance Using Dynamic Programming (Optimization in Space Complexity):

Optimized Space Complexity Solution: In the above bottom up approach we require O(m x n) space. Let’s take an observation and try to optimize our space complexity: To fill a row in DP array we require only one row i.e. the upper row. For example, if we are filling the row where i=10 in DP array then we require only values of 9th row. So we simply create a DP array of 2 x str1 length. This approach reduces the space complexity from O(N*M) to O(2*N)....

Edit Distance Using Dynamic Programming (Further Optimization in Space Complexity):

As discussed the above approach uses two 1-D arrays, now the question is can we achieve our task by using only a single 1-D array? The answer is Yes and it requires a simple observation as mentioned below:In the previous approach The curr[] array is updated using 3 values only : Value 1: curr[j] = prev[j-1] when str1[i-1] is equal to str2[j-1]Value 2: curr[j] = prev[j] when str1[i-1] is not equal to str2[j-1] Value 3: curr[j] = curr[j-1] when str1[i-1] is not equal to str2[j-1] By keeping the track of these three values we can achiever our task using only a single 1-D array...

Real-World Applications of Edit Distance:

Spell Checking and Auto-CorrectionDNA Sequence AlignmentPlagiarism DetectionNatural Language ProcessingVersion Control SystemsString Matching...

Tags:
#Amazon #edit-distance #DSA #Dynamic Programming #Amazon #Dynamic Programming

Edit Distance Using Dynamic Programming (Bottom-Up Approach):

Edit Distance Using Dynamic Programming (Further Optimization in Space Complexity):

Contact Us

Categories
Learn the most popular programming languages in the world.