forked from TheAlgorithms/Python
- Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmin_distance_up_bottom.py
49 lines (40 loc) · 1.37 KB
/
min_distance_up_bottom.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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
"""
Author : Alexander Pantyukhin
Date : October 14, 2022
This is an implementation of the up-bottom approach to find edit distance.
The implementation was tested on Leetcode: https://leetcode.com/problems/edit-distance/
Levinstein distance
Dynamic Programming: up -> down.
"""
importfunctools
defmin_distance_up_bottom(word1: str, word2: str) ->int:
"""
>>> min_distance_up_bottom("intention", "execution")
5
>>> min_distance_up_bottom("intention", "")
9
>>> min_distance_up_bottom("", "")
0
>>> min_distance_up_bottom("zooicoarchaeologist", "zoologist")
10
"""
len_word1=len(word1)
len_word2=len(word2)
@functools.cache
defmin_distance(index1: int, index2: int) ->int:
# if first word index overflows - delete all from the second word
ifindex1>=len_word1:
returnlen_word2-index2
# if second word index overflows - delete all from the first word
ifindex2>=len_word2:
returnlen_word1-index1
diff=int(word1[index1] !=word2[index2]) # current letters not identical
returnmin(
1+min_distance(index1+1, index2),
1+min_distance(index1, index2+1),
diff+min_distance(index1+1, index2+1),
)
returnmin_distance(0, 0)
if__name__=="__main__":
importdoctest
doctest.testmod()
