Skip to main content

Calculating edit distance using dynamic programming

Here given code implementation process.

/*
    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 : 2
package 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 : 2
import 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 : 2
import 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 : 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