Skip to content

Instantly share code, notes, and snippets.

@warlock2k
Created June 1, 2020 14:39
Show Gist options
  • Save warlock2k/428948095d4b54e99c82d581e7b3262c to your computer and use it in GitHub Desktop.
Save warlock2k/428948095d4b54e99c82d581e7b3262c to your computer and use it in GitHub Desktop.
import java.util.*;
class EditDistance {
public static int EditDistance(char[] a, char[] b)
{
// a & b represent two strings.
// we need to make a DP table to store values
int [][] editDistanceMemo = new int [a.length + 1][b.length + 1];
// Initialize all all elements in first row to i representing deletions.
for (int i = 0; i <= a.length; i++)
{
editDistanceMemo[i][0] = i;
}
// Initialize all all elements in first column to j representing insertions.
for (int j = 0; j <= b.length; j++)
{
editDistanceMemo[0][j] = j;
}
// Iterate through each character of a
for (int i = 1; i <= a.length; i++)
{
// Iterate through each character of b for each element of a.
for (int j = 1; j <= b.length; j++)
{
// The subproblem is to look at each character of two strings and compare them.
// Two possibilites exist, they can be equal, they need not be equal.
if (a[i-1] == b[j-1])
{
// if they are equal, then we need not count it towards edit distance.
editDistanceMemo[i][j] = editDistanceMemo[i-1][j-1] ;
}
else
{
// If they are not equal,
// then we need to check which of Insert, Replace and Delete generates the lowest edit distance and add 1 to it.
// Refer to this youtube.com/watch?v=MiqoA-yF-0M
editDistanceMemo[i][j] = 1 + Math.min(Math.min(editDistanceMemo[i-1][j], editDistanceMemo[i][j-1]), editDistanceMemo[i-1][j-1]);
}
}
}
return editDistanceMemo[a.length][b.length];
}
public static void main(String args[])
{
Scanner scan = new Scanner(System.in);
String s = scan.next();
String t = scan.next();
System.out.println(EditDistance(s.toCharArray(), t.toCharArray()));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment