Calculating edit distance using dynamic programming
Edit distance, also known as Levenshtein distance, is a metric used to measure the difference between two strings. It represents the minimum number of operations (insertions, deletions, and substitutions) required to transform one string into another. In this article, we will explore how to calculate the edit distance using dynamic programming.
Problem Statement
Given two strings, we want to calculate the edit distance between them. The edit distance is defined as the minimum number of operations required to transform one string into the other. The operations allowed are:
- Insertion: Adding a character to a string.
- Deletion: Removing a character from a string.
- Substitution: Replacing one character with another.
Pseudocode Algorithm
To calculate the edit distance between two strings using dynamic programming, we can follow these steps:
- Create a function
countEditDistancethat takes the two strings, their lengths, and a 2D arrayrecordto store the intermediate results. - If the length of one of the strings is zero, return the length of the other string.
- If the result for the current substring is already calculated and stored in the
recordarray, return that result. - If the characters at the current positions in both strings are the same, recursively call the
countEditDistancefunction for the remaining substrings. - If the characters are different, calculate the edit distances for three possible operations: insertion, deletion, and substitution. Choose the minimum of these distances and add 1 to it.
- Store the calculated result in the
recordarray. - Return the calculated result.
- Create a function
findEditDistancethat takes the two strings as input. - If one of the strings is empty, return the length of the other string.
- Create a 2D array
recordto store intermediate results, and initialize all values to -1. - Calculate the edit distance using the
countEditDistancefunction and display the result. - Repeat steps 8-11 for different test cases.
Code Solution
/*
C program for
Calculating edit distance using dynamic programming
*/
#include <stdio.h>
#include <string.h>
int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
int countEditDistance(int record[] ,
const char *first ,
const char *second,
int n, int m, int size)
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (record[((n - 1) *size) + (m - 1)] != -1)
{
// When sequence is repeated
return record[((n - 1) *size) + (m - 1)];
}
else if (first[n - 1] == second[m - 1])
{
// When n-1 and m-1 position character is equal
record[((n - 1) *size) + (m - 1)] =
countEditDistance(record, first, second, n - 1, m - 1, size);
}
else
{
int insert = countEditDistance(record, first, second, n, m - 1, size);
int remove = countEditDistance(record, first, second, n - 1, m, size);
int replace = countEditDistance(record, first, second, n - 1, m - 1, size);
record[((n - 1) *size) + (m - 1)] =
minValue(minValue(insert, replace), remove) + 1;
}
return record[((n - 1) *size) + (m - 1)];
}
void findEditDistance(const char *first , const char *second)
{
// Get the size of given string
int n = strlen(first);
int m = strlen(second);
int result = 0;
if (n == 0)
{
// When of first string empty
result = m;
}
else if (m == 0)
{
// When of second string empty
result = n;
}
else
{
// Auxiliary space
int record[(n *m) + 1];
// Set initial value is to -1
for (int i = 0; i < (n *m) + 1; ++i)
{
record[i] = -1;
}
result = countEditDistance(record, first, second, n, m, n);
}
// Display calculated results
printf("\n Given String : [%s],[%s]", first, second);
printf("\n Edit distance : %d", result);
}
int main(int argc, char
const *argv[])
{
// Test Cases
findEditDistance("man", "womans");
findEditDistance("ok", "kok");
findEditDistance("Ratings", "Reviews");
findEditDistance("Affect", "Effects");
return 0;
}Output
Given String : [man],[womans]
Edit distance : 3
Given String : [ok],[kok]
Edit distance : 1
Given String : [Ratings],[Reviews]
Edit distance : 4
Given String : [Affect],[Effects]
Edit distance : 2/*
Java Program for
Calculating edit distance using dynamic programming
*/
public class EditDistance
{
public int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
public int countEditDistance(int[] record, String first,
String second, int n, int m, int size)
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (record[((n - 1) * size) + (m - 1)] != -1)
{
// When sequence is repeated
return record[((n - 1) * size) + (m - 1)];
}
else if (first.charAt(n - 1) == second.charAt(m - 1))
{
// When n-1 and m-1 position character is equal
record[((n - 1) * size) + (m - 1)] =
countEditDistance(record, first, second, n - 1, m - 1, size);
}
else
{
int insert = countEditDistance(
record, first, second, n, m - 1, size
);
int remove = countEditDistance(
record, first, second, n - 1, m, size
);
int replace = countEditDistance(
record, first, second, n - 1, m - 1, size
);
record[((n - 1) * size) + (m - 1)] =
minValue(minValue(insert, replace),
remove
) + 1;
}
return record[((n - 1) * size) + (m - 1)];
}
public void findEditDistance(String first, String second)
{
// Get the size of given string
int n = first.length();
int m = second.length();
int result = 0;
if (n == 0)
{
// When of first string empty
result = m;
}
else if (m == 0)
{
// When of second string empty
result = n;
}
else
{
// Auxiliary space
int[] record = new int[(n * m) + 1];
// Set initial value is to -1
for (int i = 0; i < (n * m) + 1; ++i)
{
record[i] = -1;
}
result = countEditDistance(record, first, second, n, m, n);
}
// Display calculated results
System.out.print("\n Given String : [" + first + "],[" + second + "]");
System.out.print("\n Edit distance : " + result + "");
}
public static void main(String[] args)
{
EditDistance task = new EditDistance();
// Test Cases
task.findEditDistance("man", "womans");
task.findEditDistance("ok", "kok");
task.findEditDistance("Ratings", "Reviews");
task.findEditDistance("Affect", "Effects");
}
}Output
Given String : [man],[womans]
Edit distance : 3
Given String : [ok],[kok]
Edit distance : 1
Given String : [Ratings],[Reviews]
Edit distance : 4
Given String : [Affect],[Effects]
Edit distance : 2// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ Program for
Calculating edit distance using dynamic programming
*/
class EditDistance
{
public: int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
int countEditDistance(int record[], string first,
string second, int n, int m, int size)
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (record[((n - 1) *size) + (m - 1)] != -1)
{
// When sequence is repeated
return record[((n - 1) *size) + (m - 1)];
}
else if (first[n - 1] == second[m - 1])
{
// When n-1 and m-1 position character is equal
record[((n - 1) *size) + (m - 1)] =
this->countEditDistance(record, first, second, n - 1, m - 1, size);
}
else
{
int insert = this->countEditDistance(
record, first, second, n, m - 1, size
);
int remove = this->countEditDistance(
record, first, second, n - 1, m, size
);
int replace = this->countEditDistance(
record, first, second, n - 1, m - 1, size
);
record[((n - 1) *size) + (m - 1)] =
this->minValue(this->minValue(insert, replace), remove) + 1;
}
return record[((n - 1) *size) + (m - 1)];
}
void findEditDistance(string first, string second)
{
// Get the size of given string
int n = first.length();
int m = second.length();
int result = 0;
if (n == 0)
{
// When of first string empty
result = m;
}
else if (m == 0)
{
// When of second string empty
result = n;
}
else
{
// Auxiliary space
int *record = new int[(n *m) + 1];
// Set initial value is to -1
for (int i = 0; i < (n *m) + 1; ++i)
{
record[i] = -1;
}
result = this->countEditDistance(record, first, second, n, m, n);
}
// Display calculated results
cout << "\n Given String : [" << first << "],[" << second << "]";
cout << "\n Edit distance : " << result << "";
}
};
int main()
{
EditDistance *task = new EditDistance();
// Test Cases
task->findEditDistance("man", "womans");
task->findEditDistance("ok", "kok");
task->findEditDistance("Ratings", "Reviews");
task->findEditDistance("Affect", "Effects");
return 0;
}Output
Given String : [man],[womans]
Edit distance : 3
Given String : [ok],[kok]
Edit distance : 1
Given String : [Ratings],[Reviews]
Edit distance : 4
Given String : [Affect],[Effects]
Edit distance : 2// Include namespace system
using System;
/*
Csharp Program for
Calculating edit distance using dynamic programming
*/
public class EditDistance
{
public int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
public int countEditDistance(int[] record,
String first,
String second,
int n, int m, int size)
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (record[((n - 1) * size) + (m - 1)] != -1)
{
// When sequence is repeated
return record[((n - 1) * size) + (m - 1)];
}
else if (first[n - 1] == second[m - 1])
{
// When n-1 and m-1 position character is equal
record[((n - 1) * size) + (m - 1)] =
this.countEditDistance(record, first, second, n - 1, m - 1, size);
}
else
{
int insert = this.countEditDistance(
record, first, second, n, m - 1, size
);
int remove = this.countEditDistance(
record, first, second, n - 1, m, size
);
int replace = this.countEditDistance(
record, first, second, n - 1, m - 1, size
);
record[((n - 1) * size) + (m - 1)] =
this.minValue(
this.minValue(insert, replace),
remove
) + 1;
}
return record[((n - 1) * size) + (m - 1)];
}
public void findEditDistance(String first, String second)
{
// Get the size of given string
int n = first.Length;
int m = second.Length;
int result = 0;
if (n == 0)
{
// When of first string empty
result = m;
}
else if (m == 0)
{
// When of second string empty
result = n;
}
else
{
// Auxiliary space
int[] record = new int[(n * m) + 1];
// Set initial value is to -1
for (int i = 0; i < (n * m) + 1; ++i)
{
record[i] = -1;
}
result = this.countEditDistance(record, first, second, n, m, n);
}
// Display calculated results
Console.Write("\n Given String : [" + first + "],[" + second + "]");
Console.Write("\n Edit distance : " + result + "");
}
public static void Main(String[] args)
{
EditDistance task = new EditDistance();
// Test Cases
task.findEditDistance("man", "womans");
task.findEditDistance("ok", "kok");
task.findEditDistance("Ratings", "Reviews");
task.findEditDistance("Affect", "Effects");
}
}Output
Given String : [man],[womans]
Edit distance : 3
Given String : [ok],[kok]
Edit distance : 1
Given String : [Ratings],[Reviews]
Edit distance : 4
Given String : [Affect],[Effects]
Edit distance : 2package main
import "fmt"
/*
Go Program for
Calculating edit distance using dynamic programming
*/
func minValue(a, b int) int {
if a < b {
return a
}
return b
}
func countEditDistance(record[] int, first string, second string,
n int, m int, size int) int {
if m == 0 {
// When m is zero
return n
} else if n == 0 {
// When n is zero
return m
} else if record[((n - 1) * size) + (m - 1)] != -1 {
// When sequence is repeated
return record[((n - 1) * size) + (m - 1)]
} else if first[n - 1] == second[m - 1] {
// When n-1 and m-1 position character is equal
record[((n - 1) * size) + (m - 1)] = countEditDistance(record, first, second, n - 1, m - 1, size)
} else {
var insert int = countEditDistance(record, first, second, n, m - 1, size)
var remove int = countEditDistance(record, first, second, n - 1, m, size)
var replace int = countEditDistance(record, first, second, n - 1, m - 1, size)
record[((n - 1) * size) + (m - 1)] = minValue(minValue(insert, replace), remove) + 1
}
return record[((n - 1) * size) + (m - 1)]
}
func findEditDistance(first, second string) {
// Get the size of given string
var n int = len(first)
var m int = len(second)
var result int = 0
if n == 0 {
// When of first string empty
result = m
} else if m == 0 {
// When of second string empty
result = n
} else {
// Auxiliary space
// Set initial value is to -1
var record = make([] int,(n * m) + 1)
for i := 0; i < (n * m) + 1; i++ {
record[i] = -1
}
result = countEditDistance(record, first, second, n, m, n)
}
// Display calculated results
fmt.Print("\n Given String : [", first, "],[", second, "]")
fmt.Print("\n Edit distance : ", result)
}
func main() {
// Test Cases
findEditDistance("man", "womans")
findEditDistance("ok", "kok")
findEditDistance("Ratings", "Reviews")
findEditDistance("Affect", "Effects")
}Output
Given String : [man],[womans]
Edit distance : 3
Given String : [ok],[kok]
Edit distance : 1
Given String : [Ratings],[Reviews]
Edit distance : 4
Given String : [Affect],[Effects]
Edit distance : 2<?php
/*
Php Program for
Calculating edit distance using dynamic programming
*/
class EditDistance
{
public function minValue($a, $b)
{
if ($a < $b)
{
return $a;
}
return $b;
}
public function countEditDistance($record, $first,
$second, $n,
$m, $size)
{
if ($m == 0)
{
// When m is zero
return $n;
}
else if ($n == 0)
{
// When n is zero
return $m;
}
else if ($record[(($n - 1) * $size) + ($m - 1)] != -1)
{
// When sequence is repeated
return $record[(($n - 1) * $size) + ($m - 1)];
}
else if ($first[$n - 1] == $second[$m - 1])
{
// When n-1 and m-1 position character is equal
$record[(($n - 1) * $size) + ($m - 1)] =
$this->countEditDistance(
$record, $first, $second, $n - 1, $m - 1, $size
);
}
else
{
$insert = $this->countEditDistance(
$record, $first, $second, $n, $m - 1, $size
);
$remove = $this->countEditDistance(
$record, $first, $second, $n - 1, $m, $size
);
$replace = $this->countEditDistance(
$record, $first, $second, $n - 1, $m - 1, $size
);
$record[(($n - 1) * $size) + ($m - 1)] =
$this->minValue(
$this->minValue($insert, $replace), $remove
) + 1;
}
return $record[(($n - 1) * $size) + ($m - 1)];
}
public function findEditDistance($first, $second)
{
// Get the size of given string
$n = strlen($first);
$m = strlen($second);
$result = 0;
if ($n == 0)
{
// When of first string empty
$result = $m;
}
else if ($m == 0)
{
// When of second string empty
$result = $n;
}
else
{
// Auxiliary space
// Set initial value is to -1
$record = array_fill(0, ($n * $m) + 1, -1);
$result = $this->countEditDistance(
$record, $first, $second, $n, $m, $n
);
}
// Display calculated results
echo("\n Given String : [".$first."],[".$second."]");
echo("\n Edit distance : ".$result);
}
}
function main()
{
$task = new EditDistance();
// Test Cases
$task->findEditDistance("man", "womans");
$task->findEditDistance("ok", "kok");
$task->findEditDistance("Ratings", "Reviews");
$task->findEditDistance("Affect", "Effects");
}
main();Output
Given String : [man],[womans]
Edit distance : 3
Given String : [ok],[kok]
Edit distance : 1
Given String : [Ratings],[Reviews]
Edit distance : 4
Given String : [Affect],[Effects]
Edit distance : 2/*
Node JS Program for
Calculating edit distance using dynamic programming
*/
class EditDistance
{
minValue(a, b)
{
if (a < b)
{
return a;
}
return b;
}
countEditDistance(record, first, second, n, m, size)
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (record[((n - 1) * size) + (m - 1)] != -1)
{
// When sequence is repeated
return record[((n - 1) * size) + (m - 1)];
}
else if (first.charAt(n - 1) == second.charAt(m - 1))
{
// When n-1 and m-1 position character is equal
record[((n - 1) * size) + (m - 1)] =
this.countEditDistance(
record, first, second, n - 1, m - 1, size
);
}
else
{
var insert = this.countEditDistance(
record, first, second, n, m - 1, size
);
var remove = this.countEditDistance(
record, first, second, n - 1, m, size
);
var replace = this.countEditDistance(
record, first, second, n - 1, m - 1, size
);
record[((n - 1) * size) + (m - 1)] =
this.minValue(
this.minValue(insert, replace), remove
) + 1;
}
return record[((n - 1) * size) + (m - 1)];
}
findEditDistance(first, second)
{
// Get the size of given string
var n = first.length;
var m = second.length;
var result = 0;
if (n == 0)
{
// When of first string empty
result = m;
}
else if (m == 0)
{
// When of second string empty
result = n;
}
else
{
// Auxiliary space
// Set initial value is to -1
var record = Array((n * m) + 1).fill(-1);
result = this.countEditDistance(
record, first, second, n, m, n
);
}
// Display calculated results
process.stdout.write("\n Given String : [" +
first + "],[" + second + "]");
process.stdout.write("\n Edit distance : " + result);
}
}
function main()
{
var task = new EditDistance();
// Test Cases
task.findEditDistance("man", "womans");
task.findEditDistance("ok", "kok");
task.findEditDistance("Ratings", "Reviews");
task.findEditDistance("Affect", "Effects");
}
main();Output
Given String : [man],[womans]
Edit distance : 3
Given String : [ok],[kok]
Edit distance : 1
Given String : [Ratings],[Reviews]
Edit distance : 4
Given String : [Affect],[Effects]
Edit distance : 2# Python 3 Program for
# Calculating edit distance using dynamic programming
class EditDistance :
def minValue(self, a, b) :
if (a < b) :
return a
return b
def countEditDistance(self, record, first, second, n, m, size) :
if (m == 0) :
# When m is zero
return n
elif (n == 0) :
# When n is zero
return m
elif (record[((n - 1) * size) + (m - 1)] != -1) :
# When sequence is repeated
return record[((n - 1) * size) + (m - 1)]
elif (first[n - 1] == second[m - 1]) :
# When n-1 and m-1 position character is equal
record[((n - 1) * size) + (m - 1)] = self.countEditDistance(
record, first, second, n - 1, m - 1, size
)
else :
insert = self.countEditDistance(
record, first, second, n, m - 1, size
)
remove = self.countEditDistance(
record, first, second, n - 1, m, size
)
replace = self.countEditDistance(
record, first, second, n - 1, m - 1, size
)
record[((n - 1) * size) + (m - 1)] = self.minValue(
self.minValue(insert, replace), remove
) + 1
return record[((n - 1) * size) + (m - 1)]
def findEditDistance(self, first, second) :
# Get the size of given string
n = len(first)
m = len(second)
result = 0
if (n == 0) :
# When of first string empty
result = m
elif (m == 0) :
# When of second string empty
result = n
else :
# Auxiliary space
# Set initial value is to -1
record = [-1] * ((n * m) + 1)
result = self.countEditDistance(
record, first, second, n, m, n
)
# Display calculated results
print("\n Given String : [", first ,
"],[", second ,"]",
end = "",sep="")
print("\n Edit distance : ", result, end = "")
def main() :
task = EditDistance()
# Test Cases
task.findEditDistance("man", "womans")
task.findEditDistance("ok", "kok")
task.findEditDistance("Ratings", "Reviews")
task.findEditDistance("Affect", "Effects")
if __name__ == "__main__": main()Output
Given String : [man],[womans]
Edit distance : 3
Given String : [ok],[kok]
Edit distance : 1
Given String : [Ratings],[Reviews]
Edit distance : 4
Given String : [Affect],[Effects]
Edit distance : 2# Ruby Program for
# Calculating edit distance using dynamic programming
class EditDistance
def minValue(a, b)
if (a < b)
return a
end
return b
end
def countEditDistance(record, first, second, n, m, size)
if (m == 0)
# When m is zero
return n
elsif (n == 0)
# When n is zero
return m
elsif (record[((n - 1) * size) + (m - 1)] != -1)
# When sequence is repeated
return record[((n - 1) * size) + (m - 1)]
elsif (first[n - 1] == second[m - 1])
# When n-1 and m-1 position character is equal
record[((n - 1) * size) + (m - 1)] = self.countEditDistance(
record, first, second, n - 1, m - 1, size
)
else
insert = self.countEditDistance(
record, first, second, n, m - 1, size
)
remove = self.countEditDistance(
record, first, second, n - 1, m, size
)
replace = self.countEditDistance(
record, first, second, n - 1, m - 1, size
)
record[((n - 1) * size) + (m - 1)] =
self.minValue(self.minValue(insert, replace), remove) + 1
end
return record[((n - 1) * size) + (m - 1)]
end
def findEditDistance(first, second)
# Get the size of given string
n = first.length
m = second.length
result = 0
if (n == 0)
# When of first string empty
result = m
elsif (m == 0)
# When of second string empty
result = n
else
# Auxiliary space
# Set initial value is to -1
record = Array.new((n * m) + 1) {-1}
result = self.countEditDistance(record, first, second, n, m, n)
end
# Display calculated results
print("\n Given String : [", first ,"],[", second ,"]")
print("\n Edit distance : ", result)
end
end
def main()
task = EditDistance.new()
# Test Cases
task.findEditDistance("man", "womans")
task.findEditDistance("ok", "kok")
task.findEditDistance("Ratings", "Reviews")
task.findEditDistance("Affect", "Effects")
end
main()Output
Given String : [man],[womans]
Edit distance : 3
Given String : [ok],[kok]
Edit distance : 1
Given String : [Ratings],[Reviews]
Edit distance : 4
Given String : [Affect],[Effects]
Edit distance : 2import scala.collection.mutable._;
/*
Scala Program for
Calculating edit distance using dynamic programming
*/
class EditDistance()
{
def minValue(a: Int, b: Int): Int = {
if (a < b)
{
return a;
}
return b;
}
def countEditDistance(record: Array[Int],
first: String, second: String, n: Int,
m: Int, size: Int): Int = {
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (record(((n - 1) * size) + (m - 1)) != -1)
{
// When sequence is repeated
return record(((n - 1) * size) + (m - 1));
}
else if (first.charAt(n - 1) == second.charAt(m - 1))
{
// When n-1 and m-1 position character is equal
record(((n - 1) * size) + (m - 1)) = countEditDistance(
record, first, second, n - 1, m - 1, size
);
}
else
{
var insert: Int = countEditDistance(
record, first, second, n, m - 1, size
);
var remove: Int = countEditDistance(
record, first, second, n - 1, m, size
);
var replace: Int = countEditDistance(
record, first, second, n - 1, m - 1, size
);
record(((n - 1) * size) + (m - 1)) =
minValue(minValue(insert, replace), remove) + 1;
}
return record(((n - 1) * size) + (m - 1));
}
def findEditDistance(first: String, second: String): Unit = {
// Get the size of given string
var n: Int = first.length();
var m: Int = second.length();
var result: Int = 0;
if (n == 0)
{
// When of first string empty
result = m;
}
else if (m == 0)
{
// When of second string empty
result = n;
}
else
{
// Auxiliary space
// Set initial value is to -1
var record: Array[Int] = Array.fill[Int]((n * m) + 1)(-1);
result = countEditDistance(record, first, second, n, m, n);
}
// Display calculated results
print("\n Given String : [" + first + "],[" + second + "]");
print("\n Edit distance : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: EditDistance = new EditDistance();
// Test Cases
task.findEditDistance("man", "womans");
task.findEditDistance("ok", "kok");
task.findEditDistance("Ratings", "Reviews");
task.findEditDistance("Affect", "Effects");
}
}Output
Given String : [man],[womans]
Edit distance : 3
Given String : [ok],[kok]
Edit distance : 1
Given String : [Ratings],[Reviews]
Edit distance : 4
Given String : [Affect],[Effects]
Edit distance : 2import Foundation;
/*
Swift 4 Program for
Calculating edit distance using dynamic programming
*/
class EditDistance
{
func minValue(_ a: Int, _ b: Int) -> Int
{
if (a < b)
{
return a;
}
return b;
}
func countEditDistance(_ record: inout[Int], _ first: [Character], _ second:
[Character], _ n: Int, _ m: Int, _ size: Int) -> Int
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (record[((n - 1) * size) + (m - 1)] != -1)
{
// When sequence is repeated
return record[((n - 1) * size) + (m - 1)];
}
else if (first[n - 1] == second[m - 1])
{
// When n-1 and m-1 position character is equal
record[((n - 1) * size) + (m - 1)] =
self.countEditDistance(
&record, first, second, n - 1, m - 1, size
);
}
else
{
let insert: Int = self.countEditDistance(
&record, first, second, n, m - 1, size
);
let remove: Int = self.countEditDistance(
&record, first, second, n - 1, m, size
);
let replace: Int = self.countEditDistance(
&record, first, second, n - 1, m - 1, size
);
record[((n - 1) * size) + (m - 1)] =
self.minValue(self.minValue(insert, replace), remove) + 1;
}
return record[((n - 1) * size) + (m - 1)];
}
func findEditDistance(_ first: String, _ second: String)
{
// Get the size of given string
let n: Int = first.count;
let m: Int = second.count;
var result: Int = 0;
if (n == 0)
{
// When of first string empty
result = m;
}
else if (m == 0)
{
// When of second string empty
result = n;
}
else
{
// Auxiliary space
// Set initial value is to -1
var record: [Int] = Array(repeating: -1, count: (n * m) + 1);
result = self.countEditDistance(
&record, Array(first), Array(second), n, m, n
);
}
// Display calculated results
print("\n Given String : [", first ,"],[", second ,"]", terminator: "");
print("\n Edit distance : ", result, terminator: "");
}
}
func main()
{
let task: EditDistance = EditDistance();
// Test Cases
task.findEditDistance("man", "womans");
task.findEditDistance("ok", "kok");
task.findEditDistance("Ratings", "Reviews");
task.findEditDistance("Affect", "Effects");
}
main();Output
Given String : [ man ],[ womans ]
Edit distance : 3
Given String : [ ok ],[ kok ]
Edit distance : 1
Given String : [ Ratings ],[ Reviews ]
Edit distance : 4
Given String : [ Affect ],[ Effects ]
Edit distance : 2/*
Kotlin Program for
Calculating edit distance using dynamic programming
*/
class EditDistance
{
fun minValue(a: Int, b: Int): Int
{
if (a < b)
{
return a;
}
return b;
}
fun countEditDistance(record: Array < Int > ,
first: String, second: String,
n: Int, m: Int, size: Int): Int
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (record[((n - 1) * size) + (m - 1)] != -1)
{
// When sequence is repeated
return record[((n - 1) * size) + (m - 1)];
}
else if (first.get(n - 1) == second.get(m - 1))
{
// When n-1 and m-1 position character is equal
record[((n - 1) * size) + (m - 1)] =
this.countEditDistance(
record, first, second, n - 1, m - 1, size
);
}
else
{
val insert: Int = this.countEditDistance(
record, first, second, n, m - 1, size
);
val remove: Int = this.countEditDistance(
record, first, second, n - 1, m, size
);
val replace: Int = this.countEditDistance(
record, first, second, n - 1, m - 1, size
);
record[((n - 1) * size) + (m - 1)] =
this.minValue(
this.minValue(insert, replace), remove
) + 1;
}
return record[((n - 1) * size) + (m - 1)];
}
fun findEditDistance(first: String, second: String): Unit
{
// Get the size of given string
val n: Int = first.length;
val m: Int = second.length;
var result: Int ;
if (n == 0)
{
// When of first string empty
result = m;
}
else if (m == 0)
{
// When of second string empty
result = n;
}
else
{
// Auxiliary space
// Set initial value is to -1
val record: Array < Int > = Array((n * m) + 1)
{
-1
};
result = this.countEditDistance(record, first, second, n, m, n);
}
// Display calculated results
print("\n Given String : [" + first + "],[" + second + "]");
print("\n Edit distance : " + result);
}
}
fun main(args: Array < String > ): Unit
{
val task: EditDistance = EditDistance();
// Test Cases
task.findEditDistance("man", "womans");
task.findEditDistance("ok", "kok");
task.findEditDistance("Ratings", "Reviews");
task.findEditDistance("Affect", "Effects");
}Output
Given String : [man],[womans]
Edit distance : 3
Given String : [ok],[kok]
Edit distance : 1
Given String : [Ratings],[Reviews]
Edit distance : 4
Given String : [Affect],[Effects]
Edit distance : 2Code Explanation
The provided code implements the above algorithm to calculate the edit distance between two strings. It defines the countEditDistance function to recursively calculate the edit distance and store the intermediate results in the record array. The findEditDistance function initializes the record array and calls countEditDistance to get the final result. The calculated edit distances for different test cases are displayed as the output.
Resultant Output Explanation
The code is tested with different test cases:
- "man" and "womans": The edit distance is 3. The three required operations are: delete 'm', insert 'o', and insert 's'.
- "ok" and "kok": The edit distance is 1. The required operation is: substitute 'o' with 'k'.
- "Ratings" and "Reviews": The edit distance is 4. The four required operations are: substitute 'a' with 'e', insert 'e', delete 't', and insert 's'.
- "Affect" and "Effects": The edit distance is 2. The two required operations are: substitute 'a' with 'e' and insert 's'.
Time Complexity
The time complexity of the code is influenced by the size of the two input strings, n and m. Since the countEditDistance function uses memoization (storing intermediate results in the record array), it avoids redundant calculations and reduces the time complexity. Therefore, the time complexity is approximately O(n * m), where n and m are the lengths of the input strings.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment