Odległość edycyjna
Lekcja 9 z 15 w kursie Programowanie dynamiczne — podstawy w Coddy.
Odległość edycji, znana również jako odległość Levenshteina, to miara służąca do określania różnicy między dwoma ciągami znaków. Mówiąc dokładniej, jest to minimalna liczba operacji potrzebnych do przekształcenia jednego ciągu znaków w drugi.
Możliwe operacje to:
- Wstawianie: wstawienie znaku do jednego z ciągów znaków
- Usuwanie: usunięcie znaku z jednego z ciągów znaków
- Podstawianie: zastąpienie znaku w jednym z ciągów znaków innym znakiem
Odległość edycji jest szeroko stosowana w takich dziedzinach jak przetwarzanie języka naturalnego, widzenie komputerowe i bioinformatyka.
Programowanie dynamiczne można wykorzystać do efektywnego obliczania odległości edycji między dwoma ciągami znaków.
Wyzwanie
ŚredniNapisz funkcję Python edit_distance, która przyjmuje dwa ciągi znaków i zwraca odległość edycyjną między nimi.
Na przykład:
edit_distance("kitten", "sitting")powinna zwrócić 3edit_distance("intention", "execution")powinna zwrócić 5
Spróbuj swoich sił
def edit_distance(str1, str2):
# Wpisz kod tutajWszystkie lekcje w sekcji Programowanie dynamiczne — podstawy
1Wprowadzenie do programowania dynamicznego
Czym jest programowanie dynamiczne?Dlaczego jest ważne?Zastosowania w różnych dziedzinach4Zaawansowane zagadnienia
Minimalna długość podtablicyPrzycinanieOptymalizacja pamięciMaskowanie bitów3Algorytmy programowania dynamicznego
Najdłuższy wspólny podciągProblem plecakowyProblem wydawania resztyOdległość edycyjnaPoćwicz samodzielnie: Kompilator Python online