Jarak Ketik
Hitung suntingan paling sedikit untuk mengubah satu kata menjadi kata lain.
Fitur koreksi ejaan menebak kata yang kamu maksud dengan mencari kata terdekat. Kedekatan diukur dengan jarak edit: banyaknya suntingan paling sedikit untuk mengubah satu kata menjadi kata lain. Satu suntingan berarti menyisipkan, menghapus, atau mengganti satu huruf.
Masukan
Dua baris, masing-masing berisi 1 sampai 500 huruf kecil.
Keluaran
Jarak edit antara kedua kata.
Contoh masukan dan keluaran
Contoh 1
Masukan
kucing kambing
Keluaran
3
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Misalkan D[i][j] adalah jarak edit antara i huruf pertama kata A dan j huruf pertama kata B. Mengubah teks menjadi teks kosong butuh sebanyak panjangnya.
Petunjuk 2
Bila huruf terakhirnya sama, D[i][j] = D[i-1][j-1]. Selain itu, ambil 1 ditambah yang terkecil dari D[i-1][j] (hapus), D[i][j-1] (sisip), dan D[i-1][j-1] (ganti).