Jarak Edit Langkah demi Langkah
Menyisipkan, menghapus, dan mengganti untuk mengubah data
Jarak Edit Langkah demi Langkah adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang Diukur Jarak Penyuntingan
Jarak penyuntingan adalah jumlah perubahan satu karakter paling sedikit untuk mengubah satu teks menjadi teks lainnya. Nilai ini mengukur seberapa berbeda sebenarnya dua kata.
Tiga Operasi
Anda dapat menyisipkan, menghapus, atau mengganti satu karakter pada setiap perubahan. Dalam masalah standar, setiap operasi tepat bernilai satu.
Tentukan Keadaan
Misalkan dp[i][j] adalah jumlah perubahan untuk mengubah i karakter pertama A menjadi j karakter pertama B.
Kecocokan Tanpa Biaya
Jika karakter saat ini sudah cocok, tidak diperlukan perubahan. Anda cukup menyalin nilai diagonal secara langsung.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Jika Tidak, Tambahkan Satu
Ketika karakter berbeda, ambil tetangga termurah dan tambahkan satu perubahan. Minimum ditambah satu ini mencakup ketiga operasi.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Tetangga yang Mana untuk Apa
Sel di atas berarti penghapusan, sel di kiri berarti penyisipan, dan diagonal berarti penggantian. Nilai minimum cukup memilih yang termurah.
Kasus Dasar Teks Kosong
Mengubah teks sepanjang i menjadi kosong memerlukan i penghapusan. Jadi, isi baris dan kolom pertama dengan 0, 1, 2, dan seterusnya.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jTentukan Ukuran Tabel
Gunakan kisi berukuran n+1 kali m+1 agar prefiks kosong memiliki baris dan kolomnya sendiri. Penambahan batas ini membuat perulangan tetap sederhana.
dp = [[0] * (m+1) for _ in range(n+1)]Isi Berurutan
Lakukan perulangan i dan j mulai dari 1 ke atas. Setiap sel hanya bergantung pada tetangga di atas, kiri, dan diagonal yang sudah terisi.
for i in range(1, n+1):
for j in range(1, m+1):
...Baca Jaraknya
Jumlah perubahan minimum akhirnya berada di sudut. Jawaban Anda adalah dp[n][m] setelah tabel selesai.
distance = dp[n][m]Biaya dan Variasi
Proses ini membutuhkan waktu O(n kali m). Tugas nyata mungkin mengenakan biaya berbeda untuk setiap operasi, tetapi relasi rekurensi yang sama tetap berlaku.
Pemeriksaan Singkat
Karakter A[i-1] dan B[j-1] berbeda. Relasi rekurensi mana yang menghasilkan jarak penyuntingan?
Ringkasan: Jarak Penyuntingan
Kecocokan berarti menyalin diagonal; ketidakcocokan berarti 1 ditambah minimum dari tiga tetangga. Inisialisasi batas, lalu baca dp[n][m]. ✏️
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Jarak Edit Langkah demi Langkah” gratis?
Ya — teks lengkap “Jarak Edit Langkah demi Langkah” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Jarak Edit Langkah demi Langkah”?
Menyisipkan, menghapus, dan mengganti untuk mengubah data Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Jarak Edit Langkah demi Langkah” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Menghitung Jalur pada Grid
- Jumlah Jalur Minimum dengan Rintangan
- Subsekuens Sama Terpanjang
- Jarak Edit Langkah demi Langkah