Edit distance done!

It turned out my Java test cases didn't cover enough number of cases. I
added one test case for it to fail, and figured out that the range in 2
loops should start with 1.

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()))