Edit distance using recursion
The Edit Distancs problem is a classic algorithmic problem in computer science. It is also known as Levenshtein distance, and it measures the similarity between two strings by calculating the minimum number of single-character edits required to transform one string into another. The allowed edit operations are insertion, deletion, or replacement of a single character.
For example, consider the strings "kitten" and "sitting." The edit distance between them is 3, as we can transform "kitten" into "sitting" using the following operations:
- Replace 'k' with 's' (kitten → sitten)
- Replace 'e' with 'i' (sitten → sittin)
- Insert 'g' at the end (sittin → sitting)
Explanation with Example
Let's understand the edit distance using an example. Consider two strings "Saturday" and "Sunday." Our task is to calculate the edit distance between them.
-
Start with the base case: If one of the strings is empty, the edit distance will be the length of the non-empty string. For instance, if
first
is an empty string, then the edit distance would be the length ofsecond
(7 in this case). Similarly, ifsecond
is an empty string, the edit distance would be the length offirst
(8 in this case). -
If the last characters of both strings match (i.e., 'y' in "Saturday" and 'y' in "Sunday"), then we don't need to perform any edit operation on these characters. We can simply ignore them and recursively find the edit distance for the rest of the strings. In this example, the last characters match, so we will find the edit distance between "Saturda" and "Sunda."
-
If the last characters of both strings do not match, we have three options: insert, remove, or replace the character in
first
to make it equal to the character insecond
. For example, if the last character infirst
is 'r' and the last character insecond
is 'y,' we can perform one of the following operations:- Insert 'y' at the end of
first
to make it "Saturdy." - Remove 'r' from
first
to make it "Satuday." - Replace 'r' with 'y' in
first
to make it "Satuday."
- Insert 'y' at the end of
-
To find the minimum edit distance, we try all three operations recursively and choose the one that results in the smallest edit distance. The recursive function keeps breaking down the problem into smaller subproblems until it reaches the base case.
Pseudocode
The recursive algorithm for finding the edit distance can be represented as follows:
function countEditDistance(first, second, n, m):
if m == 0:
return n
else if n == 0:
return m
else if first.charAt(n - 1) == second.charAt(m - 1):
return countEditDistance(first, second, n - 1, m - 1)
else:
insert = countEditDistance(first, second, n, m - 1)
remove = countEditDistance(first, second, n - 1, m)
replace = countEditDistance(first, second, n - 1, m - 1)
return minValue(minValue(insert, replace), remove) + 1
Algorithm Explanation
The algorithm follows a recursive approach to solve the problem. It breaks the problem down into smaller subproblems and solves them recursively.
-
The function
countEditDistance
takes four parameters:first
(the first input string),second
(the second input string),n
(the length of the first string), andm
(the length of the second string). -
The base cases are checked first: if
m
is 0, it means the second string is empty, so the edit distance would be the length of the first stringn
. Similarly, ifn
is 0, it means the first string is empty, so the edit distance would be the length of the second stringm
. -
If the last characters of both strings match (i.e.,
first.charAt(n - 1) == second.charAt(m - 1)
), then we don't need to perform any edit operation on these characters. We can ignore them and recursively find the edit distance for the rest of the strings. -
If the last characters of both strings do not match, we have three options: insert, remove, or replace the character in
first
to make it equal to the character insecond
. We calculate the edit distance for each option and choose the minimum of the three as the final edit distance. -
The function returns the minimum edit distance for the current subproblem.
Program Solution
/*
C program for
Edit distance using recursion
*/
#include <stdio.h>
#include <string.h>
int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
int countEditDistance(const char *first ,
const char *second,
int n,
int m)
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (first[n - 1] == second[m - 1])
{
// When n-1 and m-1 position character is equal
return countEditDistance(first, second, n - 1, m - 1);
}
else
{
int insert = countEditDistance(first, second, n, m - 1);
int remove = countEditDistance(first, second, n - 1, m);
int replace = countEditDistance(first, second, n - 1, m - 1);
return minValue(minValue(insert, replace), remove) + 1;
}
}
void findEditDistance(const char *first , const char *second)
{
// Get the size of given string
int n = strlen(first);
int m = strlen(second);
printf("\n Given String : [%s],[%s]", first, second);
printf("\n Edit distance : %d", countEditDistance(first, second, n, m));
}
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
Edit distance using recursion
*/
public class EditDistance
{
public int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
public int countEditDistance(String first,
String second,
int n, int m)
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (first.charAt(n - 1) == second.charAt(m - 1))
{
// When n-1 and m-1 position character is equal
return countEditDistance(first, second, n - 1, m - 1);
}
else
{
int insert = countEditDistance(first, second, n, m - 1);
int remove = countEditDistance(first, second, n - 1, m);
int replace = countEditDistance(first, second, n - 1, m - 1);
return minValue(minValue(insert, replace), remove) + 1;
}
}
public void findEditDistance(String first, String second)
{
// Get the size of given string
int n = first.length();
int m = second.length();
System.out.print("\n Given String : [" +
first + "],[" + second + "]");
System.out.print("\n Edit distance : " +
countEditDistance(first, second, n, m));
}
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
Edit distance using recursion
*/
class EditDistance
{
public: int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
int countEditDistance(string first,
string second,
int n, int m)
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (first[n - 1] == second[m - 1])
{
// When n-1 and m-1 position character is equal
return this->countEditDistance(first, second, n - 1, m - 1);
}
else
{
int insert = this->countEditDistance(first, second, n, m - 1);
int remove = this->countEditDistance(first, second, n - 1, m);
int replace = this->countEditDistance(first, second, n - 1, m - 1);
return this->minValue(this->minValue(insert, replace), remove) + 1;
}
}
void findEditDistance(string first, string second)
{
// Get the size of given string
int n = first.length();
int m = second.length();
cout << "\n Given String : [" << first << "],[" << second << "]";
cout << "\n Edit distance : "
<< this->countEditDistance(first, second, n, m);
}
};
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
Edit distance using recursion
*/
public class EditDistance
{
public int minValue(int a, int b)
{
if (a < b)
{
return a;
}
return b;
}
public int countEditDistance(
String first,
String second,
int n, int m)
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (first[n - 1] == second[m - 1])
{
// When n-1 and m-1 position character is equal
return this.countEditDistance(first, second, n - 1, m - 1);
}
else
{
int insert = this.countEditDistance(first, second, n, m - 1);
int remove = this.countEditDistance(first, second, n - 1, m);
int replace = this.countEditDistance(first, second, n - 1, m - 1);
return this.minValue(this.minValue(insert, replace), remove) + 1;
}
}
public void findEditDistance(String first, String second)
{
// Get the size of given string
int n = first.Length;
int m = second.Length;
Console.Write("\n Given String : [" +
first + "],[" + second + "]");
Console.Write("\n Edit distance : " +
this.countEditDistance(first, second, n, m));
}
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
package main
import "fmt"
/*
Go Program for
Edit distance using recursion
*/
func minValue(a, b int) int {
if a < b {
return a
}
return b
}
func countEditDistance(first string, second string, n int, m int) int {
if m == 0 {
// When m is zero
return n
} else if n == 0 {
// When n is zero
return m
} else if first[n - 1] == second[m - 1] {
// When n-1 and m-1 position character is equal
return countEditDistance(first, second, n - 1, m - 1)
} else {
var insert int = countEditDistance(first, second, n, m - 1)
var remove int = countEditDistance(first, second, n - 1, m)
var replace int = countEditDistance(first, second, n - 1, m - 1)
return minValue(minValue(insert, replace), remove) + 1
}
}
func findEditDistance(first, second string) {
// Get the size of given string
var n int = len(first)
var m int = len(second)
fmt.Print("\n Given String : [", first, "],[", second, "]")
fmt.Print("\n Edit distance : ", countEditDistance(first, second, n, m))
}
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
Edit distance using recursion
*/
class EditDistance
{
public function minValue($a, $b)
{
if ($a < $b)
{
return $a;
}
return $b;
}
public function countEditDistance($first, $second, $n, $m)
{
if ($m == 0)
{
// When m is zero
return $n;
}
else if ($n == 0)
{
// When n is zero
return $m;
}
else if ($first[$n - 1] == $second[$m - 1])
{
// When n-1 and m-1 position character is equal
return $this->countEditDistance($first, $second, $n - 1, $m - 1);
}
else
{
$insert = $this->countEditDistance($first, $second, $n, $m - 1);
$remove = $this->countEditDistance($first, $second, $n - 1, $m);
$replace = $this->countEditDistance($first, $second, $n - 1, $m - 1);
return $this->minValue(
$this->minValue($insert, $replace),
$remove
) + 1;
}
}
public function findEditDistance($first, $second)
{
// Get the size of given string
$n = strlen($first);
$m = strlen($second);
echo("\n Given String : [".$first.
"],[".$second.
"]");
echo("\n Edit distance : ".
$this->countEditDistance($first, $second, $n, $m));
}
}
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
Edit distance using recursion
*/
class EditDistance
{
minValue(a, b)
{
if (a < b)
{
return a;
}
return b;
}
countEditDistance(first, second, n, m)
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (first.charAt(n - 1) == second.charAt(m - 1))
{
// When n-1 and m-1 position character is equal
return this.countEditDistance(first, second, n - 1, m - 1);
}
else
{
var insert = this.countEditDistance(first, second, n, m - 1);
var remove = this.countEditDistance(first, second, n - 1, m);
var replace = this.countEditDistance(first, second, n - 1, m - 1);
return this.minValue(this.minValue(insert, replace), remove) + 1;
}
}
findEditDistance(first, second)
{
// Get the size of given string
var n = first.length;
var m = second.length;
process.stdout.write("\n Given String : [" +
first + "],[" + second + "]");
process.stdout.write("\n Edit distance : " +
this.countEditDistance(first, second, n, m));
}
}
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
# Edit distance using recursion
class EditDistance :
def minValue(self, a, b) :
if (a < b) :
return a
return b
def countEditDistance(self, first, second, n, m) :
if (m == 0) :
# When m is zero
return n
elif (n == 0) :
# When n is zero
return m
elif (first[n - 1] == second[m - 1]) :
# When n-1 and m-1 position character is equal
return self.countEditDistance(first, second, n - 1, m - 1)
else :
insert = self.countEditDistance(first, second, n, m - 1)
remove = self.countEditDistance(first, second, n - 1, m)
replace = self.countEditDistance(first, second, n - 1, m - 1)
return self.minValue(self.minValue(insert, replace), remove) + 1
def findEditDistance(self, first, second) :
# Get the size of given string
n = len(first)
m = len(second)
print("\n Given String : [", first ,"],[", second ,"]", end = "",sep="")
print("\n Edit distance : ",
self.countEditDistance(first, second, n, m), end = "",sep="")
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
# Edit distance using recursion
class EditDistance
def minValue(a, b)
if (a < b)
return a
end
return b
end
def countEditDistance(first, second, n, m)
if (m == 0)
# When m is zero
return n
elsif (n == 0)
# When n is zero
return m
elsif (first[n - 1] == second[m - 1])
# When n-1 and m-1 position character is equal
return self.countEditDistance(first, second, n - 1, m - 1)
else
insert = self.countEditDistance(first, second, n, m - 1)
remove = self.countEditDistance(first, second, n - 1, m)
replace = self.countEditDistance(first, second, n - 1, m - 1)
return self.minValue(
self.minValue(insert, replace),
remove
) + 1
end
end
def findEditDistance(first, second)
# Get the size of given string
n = first.length
m = second.length
print("\n Given String : [", first ,"],[", second ,"]")
print("\n Edit distance : ",
self.countEditDistance(first, second, n, m))
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 : 2
import scala.collection.mutable._;
/*
Scala Program for
Edit distance using recursion
*/
class EditDistance()
{
def minValue(a: Int, b: Int): Int = {
if (a < b)
{
return a;
}
return b;
}
def countEditDistance(first: String, second:
String, n: Int, m: Int): Int = {
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (first.charAt(n - 1) == second.charAt(m - 1))
{
// When n-1 and m-1 position character is equal
return countEditDistance(first, second, n - 1, m - 1);
}
else
{
var insert: Int = countEditDistance(first, second, n, m - 1);
var remove: Int = countEditDistance(first, second, n - 1, m);
var replace: Int = countEditDistance(first, second, n - 1, m - 1);
return minValue(minValue(insert, replace), remove) + 1;
}
}
def findEditDistance(first: String, second: String): Unit = {
// Get the size of given string
var n: Int = first.length();
var m: Int = second.length();
print("\n Given String : [" + first + "],[" + second + "]");
print("\n Edit distance : " +
countEditDistance(first, second, n, m));
}
}
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 : 2
import Foundation;
/*
Swift 4 Program for
Edit distance using recursion
*/
class EditDistance
{
func minValue(_ a: Int, _ b: Int) -> Int
{
if (a < b)
{
return a;
}
return b;
}
func countEditDistance(_ first: [Character], _ second:
[Character], _ n: Int, _ m: Int) -> Int
{
if (m == 0)
{
// When m is zero
return n;
}
else if (n == 0)
{
// When n is zero
return m;
}
else if (first[n - 1] == second[m - 1])
{
// When n-1 and m-1 position character is equal
return self.countEditDistance(first, second, n - 1, m - 1);
}
else
{
let insert: Int = self.countEditDistance(first, second, n, m - 1);
let remove: Int = self.countEditDistance(first, second, n - 1, m);
let replace: Int = self.countEditDistance(first, second, n - 1, m - 1);
return self.minValue(
self.minValue(insert, replace),
remove
) + 1;
}
}
func findEditDistance(_ first: String, _ second: String)
{
// Get the size of given string
let n: Int = first.count;
let m: Int = second.count;
print("\n Given String : [",
first ,"],[", second ,"]", terminator: "");
print("\n Edit distance : ",
self.countEditDistance(Array(first),
Array(second), n, m),
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
Resultant Output Explanation
The given Java code finds and prints the edit distance for four test cases:
- "man" and "womans" → Edit distance: 3
- "ok" and "kok" → Edit distance: 1
- "Ratings" and "Reviews" → Edit distance: 4
- "Affect" and "Effects" → Edit distance: 2
The output is as expected for these test cases. It correctly calculates the minimum number of edit operations required to transform the first string into the second string.
Time Complexity
The time complexity of the given recursive solution can be analyzed using a recursive tree. The recursive tree has many overlapping subproblems, and the same subproblems are recomputed multiple times. Hence, the time complexity is exponential.
Let's denote n
as the length of the first string and m
as the length of the second
string. In the worst case, the recursive function is called three times for each pair of characters (except the
case when both characters are the same). The height of the recursive tree is n + m
, and at each
level, there are three recursive calls. Therefore, the total number of recursive calls becomes 3^(n+m), leading
to an exponential time complexity of O(3^(n+m)).
It is worth noting that the given recursive solution can be optimized using dynamic programming techniques like memoization or bottom-up approach to reduce the time complexity to O(n*m), where n and m are the lengths of the input strings. However, the provided code uses the basic recursive approach to illustrate the concept of edit distance.
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