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
• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

/*
    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;
}

 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");
	}
}

 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;
}

 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");
	}
}

 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")
}

 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();

 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();

 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()

 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()

 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");
	}
}

 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();

 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.