GeezerVison

Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,89 @@
		/**
		Author : SUBHAM SANGHAI
		A Dynamic Programming based solution for Edit Distance problem In Java
		**/

		/**Description of Edit Distance with an Example:

		Edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another,
		by counting the minimum number of operations required to transform one string into the other. The
		distance operations are the removal, insertion, or substitution of a character in the string.


		The Distance between "kitten" and "sitting" is 3. A minimal edit script that transforms the former into the latter is:

		kitten → sitten (substitution of "s" for "k")
		sitten → sittin (substitution of "i" for "e")
		sittin → sitting (insertion of "g" at the end).**/

		import java.util.Scanner;
		public class Edit_Distance
		{



		public static int minDistance(String word1, String word2)
		{
		int len1 = word1.length();
		int len2 = word2.length();
		// len1+1, len2+1, because finally return dp[len1][len2]
		int[][] dp = new int[len1 + 1][len2 + 1];
		/* If second string is empty, the only option is to
		insert all characters of first string into second*/
		for (int i = 0; i <= len1; i++)
		{
		dp[i][0] = i;
		}
		/* If first string is empty, the only option is to
		insert all characters of second string into first*/
		for (int j = 0; j <= len2; j++)
		{
		dp[0][j] = j;
		}
		//iterate though, and check last char
		for (int i = 0; i < len1; i++)
		{
		char c1 = word1.charAt(i);
		for (int j = 0; j < len2; j++)
		{
		char c2 = word2.charAt(j);
		//if last two chars equal
		if (c1 == c2)
		{
		//update dp value for +1 length
		dp[i + 1][j + 1] = dp[i][j];
		}
		else
		{
		/* if two characters are different ,
		then take the minimum of the various operations(i.e insertion,removal,substitution)*/
		int replace = dp[i][j] + 1;
		int insert = dp[i][j + 1] + 1;
		int delete = dp[i + 1][j] + 1;

		int min = replace > insert ? insert : replace;
		min = delete > min ? min : delete;
		dp[i + 1][j + 1] = min;
		}
		}
		}
		/* return the final answer , after traversing through both the strings*/
		return dp[len1][len2];
		}


		// Driver program to test above function
		public static void main(String args[])
		{
		Scanner input = new Scanner(System.in);
		String s1,s2;
		System.out.println("Enter the First String");
		s1 = input.nextLine();
		System.out.println("Enter the Second String");
		s2 = input.nextLine();
		//ans stores the final Edit Distance between the two strings
		int ans=0;
		ans=minDistance(s1,s2);
		System.out.println("The minimum Edit Distance between \"" + s1 + "\" and \"" + s2 +"\" is "+ans);
		}
		}

Add this suggestion to a batch that can be applied as a single commit. This suggestion is invalid because no changes were made to the code. Suggestions cannot be applied while the pull request is closed. Suggestions cannot be applied while viewing a subset of changes. Only one suggestion per line can be applied in a batch. Add this suggestion to a batch that can be applied as a single commit. Applying suggestions on deleted lines is not supported. You must change the existing code in this line in order to create a valid suggestion. Outdated suggestions cannot be applied. This suggestion has been applied or marked resolved. Suggestions cannot be applied from pending reviews. Suggestions cannot be applied on multi-line comments. Suggestions cannot be applied while the pull request is queued to merge. Suggestion cannot be applied right now. Please check back later.

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.