summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-22 15:11:02 -0600
committerHaidong Ji2018-12-22 15:11:02 -0600
commit33b21ee9aad03b052d14227e023b9697c6ce4a55 (patch)
tree8467cf09439a2e0ec7eae7425fb34a9f8bfaf89e
parentc023f45e82a5631319563be730f5e7aea9eee861 (diff)
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.
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/edit_distance.py30
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/edit_distanceTest.py24
2 files changed, 54 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()))
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