import java.util.Set;
import java.util.HashSet;

/**
 * Implements a solution to the classic problem Edit-Distance, also
 * know as Levenshtein Distance. You must use dynamic programming to write your
 * solution.
 */

public class EditDistance {
	/**
	 * Calculates the minimal edit-distance between s1 and s2 using the three basic
	 * operations, add, remove, and change. Strings of length 0 are valid
	 * inputs.
	 * 
	 * @param s1
	 *            The string you start with
	 * @param s2
	 *            The string to convert to
	 */
	public static int getEditCost (String s1, String s2)
	{
		return -1;
	}

	/**
	 * Computes a String representing the minimum transformation sequence from s1 to s2.
	 * The string uses the letters I, D, R, and M to stand for a sequence of 
	 * <b>I</b>nsert, <b>D</b>elete, <b>R</b>eplace and <b>M</b>atch operations.
	 * If there are multiple minimal sequences, any of them may be returned.
	 * 
	 * @param s1
	 *            The string you start with
	 * @param s2
	 *            The string to convert to
	 */
	public static String getTransformation (String s1, String s2)
	{
		return null;
	}

	/**
	 * Computes a Set of all the minimal transformations from s1 to s2. This set
	 * contains Strings in the same format as {@link #getTransformation getTransformation}.
	 * 
	 * @param s1
	 *            The string you start with
	 * @param s2
	 *            The string to convert to
	 */
	public static Set allTransformations (String s1, String s2)
	{
		// Write your code here
		// REMINDER: this method is extra credit. It is not required
		// that you implement it. If you are not planning on implementing
		// this method, please leave the method alone.
		//
		
		return null;
	}
}