Posted on by Kalkicode
Code Recursion

# 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:

1. Replace 'k' with 's' (kitten → sitten)
2. Replace 'e' with 'i' (sitten → sittin)
3. 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.

1. 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 of `second` (7 in this case). Similarly, if `second` is an empty string, the edit distance would be the length of `first` (8 in this case).

2. 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."

3. 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 in `second`. For example, if the last character in `first` is 'r' and the last character in `second` 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."
4. 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.

1. The function `countEditDistance` takes four parameters: `first` (the first input string), `second` (the second input string), `n` (the length of the first string), and `m` (the length of the second string).

2. 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 string `n`. Similarly, if `n` is 0, it means the first string is empty, so the edit distance would be the length of the second string `m`.

3. 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.

4. 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 in `second`. We calculate the edit distance for each option and choose the minimum of the three as the final edit distance.

5. 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)
{
// Test Cases
}
}``````

#### 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()
{
// Test Cases
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)
{
// Test Cases
}
}``````

#### 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()
{
// Test Cases
}
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()
{
// Test Cases
}
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() :
#  Test Cases

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()
#  Test Cases
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
}
}``````

#### 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()
{
// Test Cases
}
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:

1. "man" and "womans" → Edit distance: 3
2. "ok" and "kok" → Edit distance: 1
3. "Ratings" and "Reviews" → Edit distance: 4
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.

## Comment

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.

Categories
Relative Post