Controls
Masukkan dua string untuk menghitung jarak edit.
Jarak Edit: 2
Deskripsi
Bearcu menemukan buku resep madu kuno dengan nama-nama yang pudar. Ia perlu mengubah satu nama menjadi lain dengan operasi paling sedikit:
- Tambah satu huruf
- Hapus satu huruf
- Ganti satu huruf
Algoritma DP
Tabel DP berukuran (m+1) x (n+1):
dp[i][j]= jarak antaras[0..i-1]dant[0..j-1]dp[i][0] = i,dp[0][j] = j- Jika sama:
dp[i][j] = dp[i-1][j-1] - Jika beda:
1 + min(delete, insert, replace)
Legenda Tabel
- Jalur optimal
- Hasil akhir
Tautan Soal
DP Table
| M | O | V | I | E | ||
|---|---|---|---|---|---|---|
| L | 1 | 1 | 2 | 3 | 4 | 5 |
| O | 2 | 2 | 1 | 2 | 3 | 4 |
| V | 3 | 3 | 2 | 1 | 2 | 3 |
| E | 4 | 4 | 3 | 2 | 2 | 2 |
| 0 | 1 | 2 | 3 | 4 | 5 |