EditDistance

import java.util.Scanner;

public class EditDistance {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		System.out.println("Enter the first string :");
		String input1 = in.nextLine();
		System.out.println("Go Ahead second string :");
		String input2 = in.nextLine();
		char str1[] = input1.toCharArray();
		char str2[] = input2.toCharArray();
		System.out.println("The Max edit needed for given input is :" +identifyEditLength(str1,str2));
		

	}
	
	public static int identifyEditLength(char []str1,char[] str2)
	{
		int m = str1.length;
		int n = str2.length;
		int table[][] = new int[m+1][n+1];
		for(int i=0;i<m;i++)
		{
			table[i][0] = i;
		}
		for(int j=0;j<n;j++)
		{
			table[0][j] = j;
		}
		
		for(int i = 0;i<m;i++)
		{
			for(int j =0;j<n;j++)
			{
				if(str1[i] == str2[j])
				{
					table[i+1][j+1] = table[i][j];
				}
				else
				{
					table[i+1][j+1] = minValue(table[i][j],table[i+1][j],table[i][j+1]) + 1;
				}
			}
		}	
		tracePath(table,str1,str2);
		return table[m][n];
		
		
		
	}
	
	public static void tracePath(int[][] table, char[] str1, char[] str2)
	{
		int m = str1.length;
		int n = str2.length;
		while(m!=0 || n!=0)
		{
			if(table[m][n] == table[m-1][n-1])
			{
				m=m-1;
				n=n-1;
			}
			else if(table[m][n] == table[m-1][n] +1)
			{
				m=m-1;
				System.out.println("Deleting a character from second String --");
			}
			else if(table[m][n] == table[m][n-1] +1)
			{
				n=n-1;
				System.out.println("Deleting a character from first String --");
			}
			else if(table[m][n] == table[m-1][n-1] +1)
			{
				m=m-1;
				n=n-1;
				System.out.println("Replacing a charatcer from String 1 with String 2 --");
			}
		}
	}
	
	public static int minValue(int a, int b, int c)
	{
		int min =a;
		if(a>b)
			min =b;
		if(min > c)
			min = c;
		return min;
	}
}