diff options
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/edit_distance.py')
-rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/edit_distance.py | 30 |
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())) |