import java.util.Arrays;

public class aux4DistanciaEdicion {

	public static void main(String[] args) {
		System.out.println(dist("casa", "calle"));
	}

	static int dist(String s1, String s2) {
		int n = s1.length();
		int m = s2.length();
		int[][] A = new int[n + 1][m + 1];
		
		// rellenar primera fila y columna
		for (int i = 0; i < n + 1; i++) {
			A[i][0] = i;
		}
		for (int i = 0; i < m + 1; i++) {
			A[0][i] = i;
		}
		
		// rellenar el resto de la matriz (i,j parten de 1)
		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < m + 1; j++) {
				// el costo de modificar/reemplazar depende de si las letras son iguales o no.
				int c = 0;
				if (s1.charAt(i - 1) != s2.charAt(j - 1)) {
					c = 1;
				}
				
				A[i][j] = Math.min(A[i - 1][j] + 1, // insertar
						Math.min(A[i][j - 1] + 1, // eliminar
								A[i - 1][j - 1] + c)); // modificar/reemplazar
			}
		}
		
		// imprimir matriz para chequear
		for (int i = 0; i < A.length; i++) {
			System.out.println(Arrays.toString(A[i]));
		}
		
		return A[n][m];
	}

}