diff options
| -rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/edit_distance.py | 30 | ||||
| -rw-r--r-- | AlgoDesignAndTechniqueEdxPython/tests/edit_distanceTest.py | 24 |
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 |