|
1 | | -packageDynamicProgramming;/** |
2 | | - * Author : SUBHAM SANGHAI |
| 1 | +packageDynamicProgramming; |
| 2 | + |
| 3 | +/** |
3 | 4 | * A DynamicProgramming based solution for Edit Distance problem In Java |
4 | 5 | * Description of Edit Distance with an Example: |
5 | 6 | * <p> |
|
13 | 14 | * kitten → sitten (substitution of "s" for "k") |
14 | 15 | * sitten → sittin (substitution of "i" for "e") |
15 | 16 | * sittin → sitting (insertion of "g" at the end). |
16 | | - * Description of Edit Distance with an Example: |
17 | | - * <p> |
18 | | - * Edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another, |
19 | | - * by counting the minimum number of operations required to transform one string into the other. The |
20 | | - * distance operations are the removal, insertion, or substitution of a character in the string. |
21 | | - * <p> |
22 | | - * <p> |
23 | | - * The Distance between "kitten" and "sitting" is 3. A minimal edit script that transforms the former into the latter is: |
24 | | - * <p> |
25 | | - * kitten → sitten (substitution of "s" for "k") |
26 | | - * sitten → sittin (substitution of "i" for "e") |
27 | | - * sittin → sitting (insertion of "g" at the end). |
| 17 | + * |
| 18 | + * @author SUBHAM SANGHAI |
28 | 19 | **/ |
29 | 20 |
|
30 | | -/**Description of Edit Distance with an Example: |
31 | | -
|
32 | | - Edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another, |
33 | | - by counting the minimum number of operations required to transform one string into the other. The |
34 | | - distance operations are the removal, insertion, or substitution of a character in the string. |
35 | | -
|
36 | | -
|
37 | | - The Distance between "kitten" and "sitting" is 3. A minimal edit script that transforms the former into the latter is: |
38 | | -
|
39 | | - kitten → sitten (substitution of "s" for "k") |
40 | | - sitten → sittin (substitution of "i" for "e") |
41 | | - sittin → sitting (insertion of "g" at the end).**/ |
42 | | - |
43 | 21 | importjava.util.Scanner; |
44 | 22 |
|
45 | | -publicclassEdit_Distance { |
46 | | - |
| 23 | +publicclassEditDistance { |
47 | 24 |
|
48 | 25 | publicstaticintminDistance(Stringword1,Stringword2) { |
49 | 26 | intlen1 =word1.length(); |
@@ -87,17 +64,15 @@ then take the minimum of the various operations(i.e insertion,removal,substituti |
87 | 64 | } |
88 | 65 |
|
89 | 66 |
|
90 | | -// Driver program to test above function |
91 | | -publicstaticvoidmain(Stringargs[]) { |
| 67 | +publicstaticvoidmain(String[]args) { |
92 | 68 | Scannerinput =newScanner(System.in); |
93 | 69 | Strings1,s2; |
94 | 70 | System.out.println("Enter the First String"); |
95 | 71 | s1 =input.nextLine(); |
96 | 72 | System.out.println("Enter the Second String"); |
97 | 73 | s2 =input.nextLine(); |
98 | 74 | //ans stores the final Edit Distance between the two strings |
99 | | -intans =0; |
100 | | -ans =minDistance(s1,s2); |
| 75 | +intans =minDistance(s1,s2); |
101 | 76 | System.out.println("The minimum Edit Distance between\"" +s1 +"\" and\"" +s2 +"\" is " +ans); |
102 | 77 | } |
103 | 78 | } |