Skip to main content

Edit distance using recursion

Here given code implementation process.

/*
    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
Last updated on by Kalkicode




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.

New Comment