summaryrefslogtreecommitdiff log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
author committer Haidong Ji 2018-12-22 15:11:02 -0600 Haidong Ji 2018-12-22 15:11:02 -0600 33b21ee9aad03b052d14227e023b9697c6ce4a55 (patch) 8467cf09439a2e0ec7eae7425fb34a9f8bfaf89e c023f45e82a5631319563be730f5e7aea9eee861 (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.pynew file mode 100644index 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] = i+ + for j in range(m + 1):+ D[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.pynew file mode 100644index 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