algorithm/PuzzleCoding/src/WordEditDistance.java at master · wodgithub/algorithm · GitHub

Repository navigation

** Dynamic Programming, very similar to longest common substring question

** dis[i,j] means the distance from transform s1s2..si to t1t2...tj

** then the value of dis[i,j] should the minimus value of following:

** d[i-1, j] + deletion (just delete si to have d[i-1, j] situation)

** d[i, j-1] + insertion (base on d[i, j-1], insert tj to s become d[i, j])

** d[i-1, j-1]+substitution (base on d[i-1,j-1], replace si with tj become d[i, j])

public class WordEditDistance {

public static void main(String[] args) {

wordEditDistance("aabc", "aacc");

wordEditDistance("aabbcc", "aabb");

wordEditDistance("aabac", "abac");

wordEditDistance("algorithm", "altruistic");

}

public static void wordEditDistance(String source, String target) {

int sLen = source.length();

int tLen = target.length();

int[][] dist = new int[sLen + 1][tLen + 1];

int i = 0, j = 0;

for (i = 1; i < sLen + 1; ++i)

dist[i][0] = i;

for (j = 1; j < tLen + 1; ++j)

dist[0][j] = j;

for (i = 1; i < sLen + 1; ++i) {

for (j = 1; j < tLen + 1; ++j) {

int d1 = dist[i - 1][j] + 1;

int d2 = dist[i][j - 1] + 1;

int d3 = dist[i - 1][j - 1] + ((source.charAt(i - 1) == target.charAt(j - 1)) ? 0 : 1);

dist[i][j] = Math.min(d1, Math.min(d2, d3));

}

System.out.println(source + "->" + target + ": " + dist[sLen][tLen]);

}