GitHub Viewer

package DynamicProgramming; /** * A DynamicProgramming 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). * * @author SUBHAM SANGHAI */ import java.util.Scanner; public class EditDistance { 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 min ? min : delete; dp[i + 1][j + 1] = min; } } } /* return the final answer , after traversing through both the strings*/ return dp[len1][len2]; } 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 = minDistance(s1, s2); System.out.println( "The minimum Edit Distance between \"" + s1 + "\" and \"" + s2 + "\" is " + ans); input.close(); } }