Levenshtein edit distance
Here given code implementation process.
/*
Java Program
Levenshtein edit distance
*/
public class Distance
{
// Returns the minimum of a given three values
public int minValue(int a, int b, int c)
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
public void levenshteinDistance(String x, String y, int n, int m)
{
int[][] dp = new int[n + 1][m + 1];
// Loop controlling variables
int i = 0;
int j = 0;
// Set the value of first column
for (i = 0 ; i <= n; ++i )
{
dp[i][0] = i;
}
// Set the value of first row
for (i = 1 ; i <= m; ++i )
{
dp[0][i] = i;
}
// iterate the loop through by length of x+1
for (i = 1; i <= n; ++i)
{
// iterate the loop through by length of y+1
for (j = 1; j <= m; ++j)
{
// minValue(top, top left, and left element)
// b a
// ↖ ↑
// c ← x
dp[i][j] = minValue(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]);
if (x.charAt(i - 1) != y.charAt(j - 1))
{
dp[i][j] += 1 ;
}
}
}
// Display given text
System.out.print("\n Given x : "+x);
System.out.print("\n Given y : "+y);
// Display calculated result
System.out.print("\n Distance : " + dp[n][m]);
}
public static void main(String[] args)
{
Distance task = new Distance();
// Given text
String x = "bitterness";
String y = "buttress";
// Get the length
int n = x.length();
int m = y.length();
// Test
task.levenshteinDistance(x, y, n, m);
}
}
Output
Given x : bitterness
Given y : buttress
Distance : 3
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ Program
Levenshtein edit distance
*/
class Distance
{
public:
// Returns the minimum of a given three values
int minValue(int a, int b, int c)
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
void levenshteinDistance(string x, string y, int n, int m)
{
int dp[n + 1][m + 1];
// Loop controlling variables
int i = 0;
int j = 0;
// Set the value of first column
for (i = 0; i <= n; ++i)
{
dp[i][0] = i;
}
// Set the value of first row
for (i = 1; i <= m; ++i)
{
dp[0][i] = i;
}
// iterate the loop through by length of x+1
for (i = 1; i <= n; ++i)
{
// iterate the loop through by length of y+1
for (j = 1; j <= m; ++j)
{
// minValue(top, top left, and left element)
// b a
// ↖ ↑
// c ← x
dp[i][j] = this->minValue(
dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]
);
if (x[i - 1] != y[j - 1])
{
dp[i][j] += 1;
}
}
}
// Display given text
cout << "\n Given x : " << x;
cout << "\n Given y : " << y;
// Display calculated result
cout << "\n Distance : " << dp[n][m];
}
};
int main()
{
Distance task = Distance();
// Given text
string x = "bitterness";
string y = "buttress";
// Get the length
int n = x.length();
int m = y.length();
// Test
task.levenshteinDistance(x, y, n, m);
return 0;
}
Output
Given x : bitterness
Given y : buttress
Distance : 3
// Include namespace system
using System;
/*
C# Program
Levenshtein edit distance
*/
public class Distance
{
// Returns the minimum of a given three values
public int minValue(int a, int b, int c)
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
public void levenshteinDistance(String x, String y, int n, int m)
{
int[,] dp = new int[n + 1,m + 1];
// Loop controlling variables
int i = 0;
int j = 0;
// Set the value of first column
for (i = 0; i <= n; ++i)
{
dp[i,0] = i;
}
// Set the value of first row
for (i = 1; i <= m; ++i)
{
dp[0,i] = i;
}
// iterate the loop through by length of x+1
for (i = 1; i <= n; ++i)
{
// iterate the loop through by length of y+1
for (j = 1; j <= m; ++j)
{
// minValue(top, top left, and left element)
// b a
// ↖ ↑
// c ← x
dp[i,j] = minValue(dp[i - 1,j], dp[i - 1,j - 1], dp[i,j - 1]);
if (x[i - 1] != y[j - 1])
{
dp[i,j] += 1;
}
}
}
// Display given text
Console.Write("\n Given x : " + x);
Console.Write("\n Given y : " + y);
// Display calculated result
Console.Write("\n Distance : " + dp[n,m]);
}
public static void Main(String[] args)
{
Distance task = new Distance();
// Given text
String x = "bitterness";
String y = "buttress";
// Get the length
int n = x.Length;
int m = y.Length;
// Test
task.levenshteinDistance(x, y, n, m);
}
}
Output
Given x : bitterness
Given y : buttress
Distance : 3
<?php
/*
Php Program
Levenshtein edit distance
*/
class Distance
{
// Returns the minimum of a given three values
public function minValue($a, $b, $c)
{
if ($a > $b)
{
if ($b > $c)
{
return $c;
}
else
{
return $b;
}
}
else
{
if ($a > $c)
{
return $c;
}
else
{
return $a;
}
}
}
public function levenshteinDistance($x, $y, $n, $m)
{
$dp = array_fill(0, $n + 1, array_fill(0, $m + 1, 0));
// Loop controlling variables
$i = 0;
$j = 0;
// Set the value of first column
for ($i = 0; $i <= $n; ++$i)
{
$dp[$i][0] = $i;
}
// Set the value of first row
for ($i = 1; $i <= $m; ++$i)
{
$dp[0][$i] = $i;
}
// iterate the loop through by length of x+1
for ($i = 1; $i <= $n; ++$i)
{
// iterate the loop through by length of y+1
for ($j = 1; $j <= $m; ++$j)
{
// minValue(top, top left, and left element)
// b a
// ↖ ↑
// c ← x
$dp[$i][$j] = $this->minValue(
$dp[$i - 1][$j], $dp[$i - 1][$j - 1], $dp[$i][$j - 1]
);
if ($x[$i - 1] != $y[$j - 1])
{
$dp[$i][$j] += 1;
}
}
}
// Display given text
echo "\n Given x : ". $x;
echo "\n Given y : ". $y;
// Display calculated result
echo "\n Distance : ". $dp[$n][$m];
}
}
function main()
{
$task = new Distance();
// Given text
$x = "bitterness";
$y = "buttress";
// Get the length
$n = strlen($x);
$m = strlen($y);
$task->levenshteinDistance($x, $y, $n, $m);
}
main();
Output
Given x : bitterness
Given y : buttress
Distance : 3
/*
Node Js Program
Levenshtein edit distance
*/
class Distance
{
// Returns the minimum of a given three values
minValue(a, b, c)
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
levenshteinDistance(x, y, n, m)
{
var dp = Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
// Loop controlling variables
var i = 0;
var j = 0;
// Set the value of first column
for (i = 0; i <= n; ++i)
{
dp[i][0] = i;
}
// Set the value of first row
for (i = 1; i <= m; ++i)
{
dp[0][i] = i;
}
// iterate the loop through by length of x+1
for (i = 1; i <= n; ++i)
{
// iterate the loop through by length of y+1
for (j = 1; j <= m; ++j)
{
// minValue(top, top left, and left element)
// b a
// ↖ ↑
// c ← x
dp[i][j] = this.minValue(
dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]
);
if (x.charAt(i - 1) != y.charAt(j - 1))
{
dp[i][j] += 1;
}
}
}
// Display given text
process.stdout.write("\n Given x : " + x);
process.stdout.write("\n Given y : " + y);
// Display calculated result
process.stdout.write("\n Distance : " + dp[n][m]);
}
}
function main()
{
var task = new Distance();
// Given text
var x = "bitterness";
var y = "buttress";
// Get the length
var n = x.length;
var m = y.length;
// Test
task.levenshteinDistance(x, y, n, m);
}
main();
Output
Given x : bitterness
Given y : buttress
Distance : 3
# Python 3 Program
# Levenshtein edit distance
class Distance :
# Returns the minimum of a given three values
def minValue(self, a, b, c) :
if (a > b) :
if (b > c) :
return c
else :
return b
else :
if (a > c) :
return c
else :
return a
def levenshteinDistance(self, x, y, n, m) :
dp = [[0] * (m + 1) for _ in range(n + 1) ]
# Loop controlling variables
i = 0
j = 0
# Set the value of first column
while (i <= n) :
dp[i][0] = i
i += 1
i = 1
# Set the value of first row
while (i <= m) :
dp[0][i] = i
i += 1
i = 1
# iterate the loop through by length of x+1
while (i <= n) :
j = 1
# iterate the loop through by length of y+1
while (j <= m) :
# minValue(top, top left, and left element)
# b a
# ↖ ↑
# c ← x
dp[i][j] = self.minValue(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1])
if (x[i - 1] != y[j - 1]) :
dp[i][j] += 1
j += 1
i += 1
# Display given text
print("\n Given x : ", x, end = "")
print("\n Given y : ", y, end = "")
# Display calculated result
print("\n Distance : ", dp[n][m], end = "")
def main() :
task = Distance()
# Given text
x = "bitterness"
y = "buttress"
# Get the length
n = len(x)
m = len(y)
# Test
task.levenshteinDistance(x, y, n, m)
if __name__ == "__main__": main()
Output
Given x : bitterness
Given y : buttress
Distance : 3
# Ruby Program
# Levenshtein edit distance
class Distance
# Returns the minimum of a given three values
def minValue(a, b, c)
if (a > b)
if (b > c)
return c
else
return b
end
else
if (a > c)
return c
else
return a
end
end
end
def levenshteinDistance(x, y, n, m)
dp = Array.new(n + 1) {Array.new(m + 1) {0}}
# Loop controlling variables
i = 0
j = 0
# Set the value of first column
while (i <= n)
dp[i][0] = i
i += 1
end
i = 1
# Set the value of first row
while (i <= m)
dp[0][i] = i
i += 1
end
i = 1
# iterate the loop through by length of x+1
while (i <= n)
j = 1
# iterate the loop through by length of y+1
while (j <= m)
# minValue(top, top left, and left element)
# b a
# ↖ ↑
# c ← x
dp[i][j] = self.minValue(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1])
if (x[i - 1] != y[j - 1])
dp[i][j] += 1
end
j += 1
end
i += 1
end
# Display given text
print("\n Given x : ", x)
print("\n Given y : ", y)
# Display calculated result
print("\n Distance : ", dp[n][m])
end
end
def main()
task = Distance.new()
# Given text
x = "bitterness"
y = "buttress"
# Get the length
n = x.length
m = y.length
# Test
task.levenshteinDistance(x, y, n, m)
end
main()
Output
Given x : bitterness
Given y : buttress
Distance : 3
/*
Scala Program
Levenshtein edit distance
*/
class Distance
{
// Returns the minimum of a given three values
def minValue(a: Int, b: Int, c: Int): Int = {
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
def levenshteinDistance(x: String, y: String, n: Int, m: Int): Unit = {
var dp: Array[Array[Int]] = Array.fill[Int](n + 1, m + 1)(0);
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
// Set the value of first column
while (i <= n)
{
dp(i)(0) = i;
i += 1;
}
i = 1;
// Set the value of first row
while (i <= m)
{
dp(0)(i) = i;
i += 1;
}
i = 1;
// iterate the loop through by length of x+1
while (i <= n)
{
j = 1;
// iterate the loop through by length of y+1
while (j <= m)
{
// minValue(top, top left, and left element)
// b a
// ↖ ↑
// c ← x
dp(i)(j) = this.minValue(
dp(i - 1)(j), dp(i - 1)(j - 1), dp(i)(j - 1)
);
if (x.charAt(i - 1) != y.charAt(j - 1))
{
dp(i)(j) += 1;
}
j += 1;
}
i += 1;
}
// Display given text
print("\n Given x : " + x);
print("\n Given y : " + y);
// Display calculated result
print("\n Distance : " + dp(n)(m));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Distance = new Distance();
// Given text
var x: String = "bitterness";
var y: String = "buttress";
// Get the length
var n: Int = x.length();
var m: Int = y.length();
// Test
task.levenshteinDistance(x, y, n, m);
}
}
Output
Given x : bitterness
Given y : buttress
Distance : 3
import Foundation
/*
Swift 4 Program
Levenshtein edit distance
*/
class Distance
{
// Returns the minimum of a given three values
func minValue(_ a: Int, _ b: Int, _ c: Int)->Int
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
func levenshteinDistance(_ x1: String, _ y1: String, _ n: Int, _ m: Int)
{
let x = Array(x1);
let y = Array(y1);
var dp: [[Int]] =
Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1);
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
// Set the value of first column
while (i <= n)
{
dp[i][0] = i;
i += 1;
}
i = 1;
// Set the value of first row
while (i <= m)
{
dp[0][i] = i;
i += 1;
}
i = 1;
// iterate the loop through by length of x+1
while (i <= n)
{
j = 1;
// iterate the loop through by length of y+1
while (j <= m)
{
// minValue(top, top left, and left element)
// b a
// ↖ ↑
// c ← x
dp[i][j] = self.minValue(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]);
if (x[i - 1] != y[j - 1])
{
dp[i][j] += 1;
}
j += 1;
}
i += 1;
}
// Display given text
print("\n Given x : ", x1, terminator: "");
print("\n Given y : ", y1, terminator: "");
// Display calculated result
print("\n Distance : ", dp[n][m], terminator: "");
}
}
func main()
{
let task: Distance = Distance();
// Given text
let x: String = "bitterness";
let y: String = "buttress";
// Get the length
let n: Int = x.count;
let m: Int = y.count;
// Test
task.levenshteinDistance(x, y, n, m);
}
main();
Output
Given x : bitterness
Given y : buttress
Distance : 3
/*
Kotlin Program
Levenshtein edit distance
*/
class Distance
{
// Returns the minimum of a given three values
fun minValue(a: Int, b: Int, c: Int): Int
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
fun levenshteinDistance(x: String, y: String, n: Int, m: Int): Unit
{
var dp: Array < Array < Int >> = Array(n + 1)
{
Array(m + 1)
{
0
}
};
// Loop controlling variables
var i: Int = 0;
var j: Int ;
// Set the value of first column
while (i <= n)
{
dp[i][0] = i;
i += 1;
}
i = 1;
// Set the value of first row
while (i <= m)
{
dp[0][i] = i;
i += 1;
}
i = 1;
// iterate the loop through by length of x+1
while (i <= n)
{
j = 1;
// iterate the loop through by length of y+1
while (j <= m)
{
// minValue(top, top left, and left element)
// b a
// ↖ ↑
// c ← x
dp[i][j] = this.minValue(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]);
if (x.get(i - 1) != y.get(j - 1))
{
dp[i][j] += 1;
}
j += 1;
}
i += 1;
}
// Display given text
print("\n Given x : " + x);
print("\n Given y : " + y);
// Display calculated result
print("\n Distance : " + dp[n][m]);
}
}
fun main(args: Array < String > ): Unit
{
var task: Distance = Distance();
// Given text
var x: String = "bitterness";
var y: String = "buttress";
// Get the length
var n: Int = x.length;
var m: Int = y.length;
// Test
task.levenshteinDistance(x, y, n, m);
}
Output
Given x : bitterness
Given y : buttress
Distance : 3

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