From 33b21ee9aad03b052d14227e023b9697c6ce4a55 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sat, 22 Dec 2018 15:11:02 -0600
Subject: 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.---
 .../sources/edit_distance.py                       | 30 ++++++++++++++++++++++
 .../tests/edit_distanceTest.py                     | 24 +++++++++++++++++
 2 files changed, 54 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/edit_distance.py
 create mode 100644 AlgoDesignAndTechniqueEdxPython/tests/edit_distanceTest.py

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()))
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/edit_distanceTest.py b/AlgoDesignAndTechniqueEdxPython/tests/edit_distanceTest.py
new file mode 100644
index 0000000..4ffdc1f
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/edit_distanceTest.py
@@ -0,0 +1,24 @@
+'''
+Created on Dec 21, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.edit_distance import editDistance
+
+class Test(unittest.TestCase):
+
+
+    def testEditDistance(self):
+        self.assertEqual(0, editDistance("ab", "ab"))
+        self.assertEqual(3, editDistance("short", "ports"))
+        self.assertEqual(5, editDistance("editing", "distance"))
+    
+    def testEditDistance1(self):
+        self.assertEqual(1, editDistance("a", "x"))
+
+
+if __name__ == "__main__":
+    #import sys;sys.argv = ['', 'Test.testEditDistance']
+    unittest.main()
\ No newline at end of file
-- 
cgit v1.2.3