summaryrefslogtreecommitdiff
path: root/AlgoDesignAndTechniqueEdxJava/sources/EditDistance.java
diff options
context:
space:
mode:
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava/sources/EditDistance.java')
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/EditDistance.java43
1 files changed, 43 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/EditDistance.java b/AlgoDesignAndTechniqueEdxJava/sources/EditDistance.java
new file mode 100644
index 0000000..640d6e3
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/EditDistance.java
@@ -0,0 +1,43 @@
+import java.util.Scanner;
+
+public class EditDistance {
+
+ public static void main(String args[]) {
+ Scanner scan = new Scanner(System.in);
+
+ String s = scan.next();
+ String t = scan.next();
+
+ System.out.println(editDistance(s, t));
+ }
+
+ public static int editDistance(String A, String B) {
+ int m = B.length();
+ int n = A.length();
+ int[][] D = new int[n + 1][m + 1];
+
+ for (int i = 0; i < n + 1; i++) {
+ D[i][0] = i;
+ }
+ for (int j = 0; j < m + 1; j++) {
+ D[0][j] = j;
+ }
+
+ for (int j = 1; j < m + 1; j++) {
+ for (int i = 1; i < n + 1; i++) {
+ int insertion = D[i][j - 1] + 1;
+ int deletion = D[i - 1][j] + 1;
+ int match = D[i - 1][j - 1];
+ int mismatch = D[i - 1][j - 1] + 1;
+ if (A.toCharArray()[i - 1] == B.toCharArray()[j - 1]) {
+ D[i][j] = Math.min(insertion, Math.min(deletion, match));
+ } else {
+ D[i][j] = Math.min(insertion, Math.min(deletion, mismatch));
+ }
+ }
+ }
+
+ return D[n][m];
+ }
+
+}