import java.io.*;
import java.util.*;

public class Assignment2b {

    public static int f(int i, int j, String str1, String str2){
        if(str1.charAt(i-1)==str2.charAt(j-1))
        return 0;
        else return 1;
    }

    public static void main(String[] args){

        System.out.print("Enter one of two strings to be compared: ");
        Scanner scan = new Scanner(System.in);
        String s1= scan.nextLine();
        System.out.print("Enter string to be compared to " + s1 + ": ");
        String s2= scan.nextLine();
        System.out.println("Strings to be compared: " + s1 + " to " + s2);
        int distance=0;

        int len1 = s1.length();
        int len2 = s2.length();

        int m[][]=new int[len1+1][len2+1];
        //offset first letter of s2
        System.out.print("    ");
        int z=0;
        for(int i = 1; i < len1+1; i++) {
            m[i][0] = i;
        }
        for(int j = 1; j<len2+1;j++) {
            m[0][j] = j;
            //outputs word s2 on top of grid
            if(z!=len2) {
                System.out.print(s2.charAt(z) + " ");
                z++;
            }
        }
        System.out.println();

        //start distance formula
        for(int i =1; i < len1+1; i++) {
            for(int j=1; j < len2+1; j++) {
                distance=m[i][j]=Math.min(m[i-1][j-1]+f(i,j,s1,s2),Math.min(m[i-1][j]+1,m[i][j-1]+1));
            }
        }

        z=0;
        for(int i = 0; i < len1+1; i++) {
            //printing s1 on side of grid since correct length position
            if(i==0)
                System.out.print("  ");
            if(z != len1 && i!=0) {
                System.out.print(s1.charAt(z)+ " ");
                z++;
            }
            for(int j = 0; j<len2+1;j++) {
                System.out.print(m[i][j]+" ");
            }
            System.out.println();
        }



        System.out.println("Their distance is " + distance);
    }

}