-
Notifications
You must be signed in to change notification settings - Fork 39
/
solution_31.py
29 lines (24 loc) · 925 Bytes
/
solution_31.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def coding_problem_31(s, t, debt=0):
"""
Given two strings, compute the edit distance between them.
The edit distance between two strings refers to the minimum number of character insertions, deletions, and
substitutions required to change one string to the other.
Example:
>>> coding_problem_31("kitten", "sitting") # k>>s, e>>i, +g
3
>>> coding_problem_31("kitten", "cat") # k>>c, i>>a, -ten
5
>>> coding_problem_31("black", "white")
5
>>> coding_problem_31("top", "dog")
2
"""
if not s or not t:
return len(s) + len(t) + debt
i = coding_problem_31(s, t[1:], debt + 1) # insertion
d = coding_problem_31(s[1:], t, debt + 1) # deletion
s = coding_problem_31(s[1:], t[1:], debt + (s[0] != t[0])) # substitution / matching character
return min(i, d, s)
if __name__ == '__main__':
import doctest
doctest.testmod(verbose=True)