summaryrefslogtreecommitdiff
path: root/AlgoDesignAndTechniqueEdxPython/sources/edit_distance.py
diff options
context:
space:
mode:
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/edit_distance.py')
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/edit_distance.py30
1 files changed, 30 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/edit_distance.py b/AlgoDesignAndTechniqueEdxPython/sources/edit_distance.py
new file mode 100644
index 0000000..de6c8dc
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/edit_distance.py
@@ -0,0 +1,30 @@
+# Uses python3
+def editDistance(A, B):
+ m = len(B)
+ n = len(A)
+# Matrix = [[0 for x in range(w)] for y in range(h)]
+# https://stackoverflow.com/questions/6667201/how-to-define-a-two-dimensional-array-in-python
+ D = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
+
+ for i in range(n + 1):
+ D[i][0] = i
+
+ for j in range(m + 1):
+ D[0][j] = j
+
+ # watch out here, range starts at 1!
+ for j in range(1, m + 1):
+ for i in range(1, n + 1):
+ insertion = D[i][j - 1] + 1
+ deletion = D[i - 1][j] + 1
+ match = D[i - 1][j - 1]
+ mismatch = D[i - 1][j - 1] + 1
+ if A[i - 1] == B[j - 1]:
+ D[i][j] = min(insertion, deletion, match)
+ else:
+ D[i][j] = min(insertion, deletion, mismatch)
+ return D[n][m]
+
+
+if __name__ == "__main__":
+ print(editDistance(input(), input()))