public class LD {
	public static void main(String[] args) {
		// Testing Kitten & Sitting...
		String s1 = "kitten";
		String s2 = "sitting";
		System.out.println(computeLD(s1, s2, s1.length(), s2.length()));

	}

	public static int computeLD(String s1, String s2, int s1_l, int s2_l) {
		int cost = 0;
		if (s1_l == 0) return s1_l;
		if (s2_l == 0) return s2_l;
		if (s1.charAt(s1_l-1) == s2.charAt(s2_l-1)) cost = 0; else cost = 1;
		return Math.min(Math.min(computeLD(s1,s2,s1_l-1,s2_l)+1,computeLD(s1,s2,s1_l,s2_l-1)+1),computeLD(s1,s2,s1_l-1,s2_l-1)+cost);
	}
}