Jarak Suntingan Langkah demi Langkah
Sisip, padam dan ganti untuk membuat transformasi.
Jarak Suntingan Langkah demi Langkah ialah pelajaran Competitive Programming Academy percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Competitive Programming Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Perkara yang Diukur oleh Jarak Suntingan
Jarak suntingan ialah bilangan suntingan satu aksara yang paling sedikit untuk menukar satu rentetan kepada rentetan yang lain. Ia mengukur sejauh mana perbezaan sebenar antara dua perkataan.
Tiga Operasi
Anda boleh menyisipkan, memadam atau menggantikan satu aksara bagi setiap suntingan. Setiap operasi berharga tepat satu dalam masalah piawai.
Tentukan Keadaan
Biarkan dp[i][j] menjadi bilangan suntingan untuk menukar i aksara pertama A kepada j aksara pertama B.
Padanan Percuma
Jika aksara semasa sudah sepadan, tiada suntingan diperlukan. Anda hanya membawa nilai diagonal terus ke bawah.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Jika Tidak, Bayar Satu
Apabila aksara berbeza, ambil jiran yang paling murah dan tambah satu suntingan. Minimum tambah satu ini merangkumi ketiga-tiga operasi.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Jiran yang Mana Satu
Sel di atas ialah padam, sel di kiri ialah sisip, dan diagonal ialah ganti. Minimum hanya memilih yang paling murah.
Kes Asas Rentetan Kosong
Menukar rentetan yang panjangnya i kepada rentetan kosong memerlukan i pemadaman. Jadi isi baris dan lajur 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] = jUkur Saiz Jadual
Gunakan jadual n+1 darab m+1 supaya awalan kosong mendapat baris dan lajurnya sendiri. Pengalas ini memastikan gelung kekal mudah.
dp = [[0] * (m+1) for _ in range(n+1)]Isi Mengikut Susunan
Ulang i dan j ke atas bermula dari 1. Setiap sel hanya bergantung pada jiran di atas, kiri dan diagonal yang sudah diisi.
for i in range(1, n+1):
for j in range(1, m+1):
...Baca Jaraknya
Bilangan minimum suntingan akhirnya berada di penjuru. Jawapan anda ialah dp[n][m] selepas jadual lengkap.
distance = dp[n][m]Kos dan Variasi
Ini berjalan dalam masa O(n darab m). Tugasan sebenar mungkin mengenakan kos berbeza bagi setiap operasi, tetapi rumus rekuren yang sama masih berfungsi.
Semakan Pantas
Aksara A[i-1] dan B[j-1] berbeza. Rumus rekuren manakah yang memberikan jarak suntingan?
Imbas Kembali: Jarak Suntingan
Padanan bermaksud bawa nilai diagonal; ketidakpadanan bermaksud 1 ditambah minimum tiga jiran. Tetapkan sempadan, kemudian baca dp[n][m]. ✏️
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Jarak Suntingan Langkah demi Langkah” percuma?
Ya — teks penuh “Jarak Suntingan Langkah demi Langkah” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Competitive Programming Academy, tingkat taraf kepada CoddyKit PRO. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Jarak Suntingan Langkah demi Langkah”?
Sisip, padam dan ganti untuk membuat transformasi. Anda berlatih Competitive Programming Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Competitive Programming Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Competitive Programming Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Jarak Suntingan Langkah demi Langkah” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Pengiraan Laluan pada Grid
- Jumlah Laluan Minimum dengan Halangan
- Subjujukan Sepunya Terpanjang
- Jarak Suntingan Langkah demi Langkah