gistfile1.java

import java.util.LinkedList;

public class LevenshteinDistance {

	public static final int NONE = 0;
	public static final int DELETE = 1;
	public static final int INSERT = 2;
	public static final int CHANGE = 3;
	
	private static int minimum(int a, int b, int c) {
		return Math.min(Math.min(a, b), c);
	}

	public static int[][] distanceMatrix(CharSequence str1,
			CharSequence str2) {
		int[][] distance = new int[str1.length() + 1][str2.length() + 1];

		for (int i = 0; i <= str1.length(); i++)
			distance[i][0] = i;
		for (int j = 1; j <= str2.length(); j++)
			distance[0][j] = j;

		for (int i = 1; i <= str1.length(); i++)
			for (int j = 1; j <= str2.length(); j++)
				distance[i][j] = minimum(
						distance[i - 1][j] + 1, //Delete
						distance[i][j - 1] + 1, //Insert
						distance[i - 1][j - 1]
								+ ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0
										: 1)); // Change/None

		return distance;
	}

	
	public static int computeLevenshteinDistance(CharSequence str1,
			CharSequence str2) {
		return distanceMatrix(str1, str2)[str1.length()][str2.length()];
	}
	
	public static int[] getOperations(CharSequence str1,
			CharSequence str2) {
		LinkedList<Integer> ops = new LinkedList<Integer>();
		
		int[][] matrix = distanceMatrix(str1, str2);
		
		int x = str1.length();
		int y = str2.length();
		while (x>0 && y>0){
			if (x>0 && matrix[x][y] == matrix[x-1][y]+1){
				x--;
				ops.add(DELETE);
			} else if (y>0 && matrix[x][y] == matrix[x][y-1]+1) {
				y--;
				ops.add(INSERT); 
			} else if (matrix[x][y] == matrix[x-1][y-1]+1){
				x--;
				y--;
				ops.add(CHANGE); // from str1.charAt(x+1) to str2.charAt(y+1)
			} else {
				x--;
				y--;
				ops.add(NONE);
			}
		}
		
		
		int[] result = new int[ops.size()];
		for (int i = 0; i < result.length; i++) {
			result[result.length - i - 1] = ops.get(i);
		}
		return result;
	}
	
	
}