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
Below is the code implementation of the approach:
// 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 str1, string str2)
{
int m = str1.size();
int n = str2.size();
int previous;
vector<int> curr(n + 1, 0);
for (int j = 0; j <= n; j++) {
curr[j] = j;
}
for (int i = 1; i <= m; i++) {
previous = curr[0];
curr[0] = i;
for (int j = 1; j <= n; j++) {
int temp = curr[j];
if (str1[i - 1] == str2[j - 1]) {
curr[j] = previous;
}
else {
curr[j] = 1
+ min({ previous, curr[j - 1],
curr[j] });
}
previous = temp;
}
}
return curr[n];
}
};
int main()
{
string str1 = "GEEXSFRGEEKKS", str2 = "w3wiki";
Solution ob;
int ans = ob.editDistance(str1, str2);
cout << ans << "\n";
return 0;
}
public class EditDistance {
// This method calculates the edit distance (Levenshtein
// distance) between two strings.
public int editDistance(String str1, String str2)
{
// Get the lengths of the two input strings.
int m = str1.length();
int n = str2.length();
// Initialize an array to store the current row of
// edit distances.
int[] curr = new int[n + 1];
// Initialize the first row with values 0 to n.
for (int j = 0; j <= n; j++) {
curr[j] = j;
}
int previous;
for (int i = 1; i <= m; i++) {
// Store the value of the previous row's first
// column.
previous = curr[0];
curr[0] = i;
for (int j = 1; j <= n; j++) {
// Store the current value before updating
// it.
int temp = curr[j];
// Check if the characters at the current
// positions in str1 and str2 are the same.
if (str1.charAt(i - 1)
== str2.charAt(j - 1)) {
// If they are the same, no additional
// cost is incurred.
curr[j] = previous;
}
else {
// If the characters are different,
// calculate the minimum of three
// operations:
// 1. Deletion (previous value)
// 2. Insertion (current row's previous
// value)
// 3. Substitution (diagonal previous
// value)
curr[j] = 1 + Math.min(
Math.min(previous, curr[j - 1]), curr[j]);
}
// Update the previous value to the stored
// temporary value.
previous = temp;
}
}
// The value in the last cell of the current row
// represents the edit distance.
return curr[n];
}
public static void main(String[] args)
{
String str1 = "GEEXSFRGEEKKS";
String str2 = "w3wiki";
EditDistance ed = new EditDistance();
int ans = ed.editDistance(str1, str2);
System.out.println(ans);
}
}
def editDistance(str1, str2):
# Get the lengths of the input strings
m = len(str1)
n = len(str2)
# Initialize a list to store the current row
curr = [0] * (n + 1)
# Initialize the first row with values from 0 to n
for j in range(n + 1):
curr[j] = j
# Initialize a variable to store the previous value
previous = 0
# Loop through the rows of the dynamic programming matrix
for i in range(1, m + 1):
# Store the current value at the beginning of the row
previous = curr[0]
curr[0] = i
# Loop through the columns of the dynamic programming matrix
for j in range(1, n + 1):
# Store the current value in a temporary variable
temp = curr[j]
# Check if the characters at the current positions in str1 and str2 are the same
if str1[i - 1] == str2[j - 1]:
curr[j] = previous
else:
# Update the current cell with the minimum of the three adjacent cells
curr[j] = 1 + min(previous, curr[j - 1], curr[j])
# Update the previous variable with the temporary value
previous = temp
# The value in the last cell represents the minimum number of operations
return curr[n]
# Driver Code
if __name__ == "__main__":
str1 = "GEEXSFRGEEKKS"
str2 = "w3wiki"
ans = editDistance(str1, str2)
print(ans)
using System;
class GFG {
// Function to calculate the minimum edit distance
// between two strings
static int EditDistance(string str1, string str2)
{
// Get the length of the first string
int m = str1.Length;
// Get the length of the second string
int n = str2.Length;
// Initialize an array to store the current row
int[] curr = new int[n + 1];
for (int j = 0; j <= n; j++) {
// Initialize the first row with values from 0
// to n
curr[j] = j;
}
// Initialize a variable to store the previous value
int previous = 0;
for (int i = 1; i <= m; i++) {
// Store the current value at the beginning of
// the row
previous = curr[0];
// Update the first element of the current row
curr[0] = i;
for (int j = 1; j <= n; j++) {
// Store the current value in a temporary
// variable
int temp = curr[j];
if (str1[i - 1] == str2[j - 1]) {
// Characters are the same, no operation
// needed
curr[j] = previous;
}
else {
// Update the current cell with the
// minimum of the three adjacent cells
curr[j]
= 1
+ Math.Min(previous,
Math.Min(curr[j - 1],
curr[j]));
}
// Update the previous variable with the
// temporary value
previous = temp;
}
}
// The value in the last cell represents the minimum
// number of operations
return curr[n];
}
// Driver Code
static void Main(string[] args)
{
string str1 = "GEEXSFRGEEKKS";
string str2 = "w3wiki";
// Calculate the edit distance
int ans = EditDistance(str1, str2);
Console.WriteLine(ans);
}
}
function editDistance(str1, str2) {
// Get the lengths of the input strings
const m = str1.length;
const n = str2.length;
// Initialize an array to store the current row
const curr = new Array(n + 1).fill(0);
// Initialize the first row with values from 0 to n
for (let j = 0; j <= n; j++) {
curr[j] = j;
}
// Initialize a variable to store the previous value
let previous = 0;
// Loop through the rows of the dynamic programming matrix
for (let i = 1; i <= m; i++) {
// Store the current value at the beginning of the row
previous = curr[0];
curr[0] = i;
// Loop through the columns of the dynamic programming matrix
for (let j = 1; j <= n; j++) {
// Store the current value in a temporary variable
const temp = curr[j];
// Check if the characters at the current positions in str1 and str2 are the same
if (str1[i - 1] === str2[j - 1]) {
curr[j] = previous;
} else {
// Update the current cell with the minimum of the three adjacent cells
curr[j] = 1 + Math.min(previous, curr[j - 1], curr[j]);
}
// Update the previous variable with the temporary value
previous = temp;
}
}
// The value in the last cell represents the minimum number of operations
return curr[n];
}
// Driver Code
const str1 = "GEEXSFRGEEKKS";
const str2 = "w3wiki";
const ans = editDistance(str1, str2);
console.log(ans);
Output
3
Time Complexity: O(M*N)
Auxiliary Space: O(N)
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.
Contact Us