Jarak edit
Pelajaran 9 dari 15 dalam kursus Dasar-Dasar Pemrograman Dinamis di Coddy.
Jarak edit, yang juga dikenal sebagai jarak Levenshtein, adalah metrik yang digunakan untuk mengukur perbedaan antara dua string. Secara khusus, jarak ini adalah jumlah minimum operasi yang diperlukan untuk mengubah satu string menjadi string lainnya.
Operasi yang dapat dilakukan adalah:
- Penyisipan: Menyisipkan karakter ke dalam salah satu string
- Penghapusan: Menghapus karakter dari salah satu string
- Substitusi: Mengganti karakter dalam salah satu string dengan karakter lain
Jarak edit banyak digunakan dalam bidang seperti pemrosesan bahasa alami, visi komputer, dan bioinformatika.
Pemrograman dinamis dapat digunakan untuk menghitung jarak edit antara dua string secara efisien.
Tantangan
SedangTulis fungsi Python edit_distance yang menerima dua string dan mengembalikan jarak edit di antara keduanya.
Contoh:
edit_distance("kitten", "sitting")seharusnya mengembalikan 3edit_distance("intention", "execution")seharusnya mengembalikan 5
Coba sendiri
def edit_distance(str1, str2):
# Tulis kodemu di siniSemua pelajaran di Dasar-Dasar Pemrograman Dinamis
3Algoritma pemrograman dinamis
Subsekuens bersama terpanjangMasalah knapsackMasalah penukaran koinJarak editLatihan sendiri: Compiler Python online