package tools;
import java.util.*;


public class StringCompare {
	private static int [] [] d ;
	private static String a, b ;
	
	private static int calc(int ia, int ib) {
		if (ia < 0 || ib < 0) return 0 ;
		if (d [ia] [ib] != -1) return d [ia] [ib] ;
		if (ia == 0) {
			d [ia] [ib] = ib ;
		}
		else
			if (ib == 0) {
				d [ia] [ib] = ia ;
			}
			else {
				if (a.charAt(ia - 1) == b.charAt(ib - 1))
					d [ia] [ib] = calc(ia - 1, ib - 1) ;
				else
					d [ia] [ib] = calc(ia - 1, ib - 1) + 1 ;
				d [ia] [ib] = Math.min(d [ia] [ib], 
						Math.min(calc(ia - 1, ib) + 1, calc(ia, ib - 1) + 1)) ;
			}
		return d [ia] [ib] ;
	}
	public static int editDistance(String _a, String _b) {
		a = new String(_a) ;
		b = new String(_b) ;
		
		d = new int [a.length() + 1] [b.length() + 1] ;
		for (int i = 0 ; i <= a.length() ; i ++)
			Arrays.fill(d [i], -1) ;
		d [0] [0] = 0 ;
		int tmp = calc(a.length(), b.length()) ;
		return calc(a.length(), b.length()) ;
	}
}