Question

/* Write a recursive function named editDistance that accepts two string

   * parameters and returns the "edit distance" between the two strings as an

   * integer. Edit distance (also called Levenshtein distance) is the minimum

   * number of "changes" required to get from s1 to s2 or vice versa. A "change"

   * is a) inserting a character,

   * b) deleting a character, or

   * c) changing a character to a different character.

   *

   * Some examples:

   * editDistance("driving", "diving") -> 1

   * editDistance("debate", "irate") -> 3

   * editDistance("football", "cookies") -> 6

   */

public static int editDistance(String s1, String s2) {

return -1;

}

Answer 1

/* Here is your code*/

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main
{
public static int editDistance(String s1, String s2)
{ String a=s1,b=s2;
a = a.toLowerCase();
b = b.toLowerCase();
int[] costs = new int[b.length() + 1];
for (int j = 0; j < costs.length; j++)
costs[j] = j;
for (int i = 1; i <= a.length(); i++)
{
costs[0] = i;
int nw = i - 1;
for (int j = 1; j <= b.length(); j++)
{
int cj = Math.min(1 + Math.min(costs[j], costs[j - 1]),
a.charAt(i - 1) == b.charAt(j - 1) ? nw : nw + 1);
nw = costs[j];
costs[j] = cj;
}
}
return costs[b.length()];
}

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
String text="";
  
System.out.print(editDistance("football", "cookies"));

}
}