/
xddxdd
/
Python
Обзор
Документация
Войти
/
xddxdd
/
Python
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
dynamic_programming/min_distance_up_bottom.py
49 строк
1 KB
pre-commit-ci[bot]
[pre-commit.ci] pre-commit autoupdate (#9543)
07 окт 2023, 22:32
Не верифицирован
07 окт 2023, 22:32
895dffb
Код
Авторство
О чём код?
""" 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. """ import functools def min_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 def min_distance(index1: int, index2: int) -> int: # if first word index overflows - delete all from the second word if index1 >= len_word1: return len_word2 - index2 # if second word index overflows - delete all from the first word if index2 >= len_word2: return len_word1 - index1 diff = int(word1[index1] != word2[index2]) # current letters not identical return min( 1 + min_distance(index1 + 1, index2), 1 + min_distance(index1, index2 + 1), diff + min_distance(index1 + 1, index2 + 1), ) return min_distance(0, 0) if __name__ == "__main__": import doctest doctest.testmod()