Watak Tambahan dalam Rentetan
2707. Watak Tambahan dalam Rentetan
Kesukaran: Sederhana
Topik: Tatasusunan, Jadual Cincang, Rentetan, Pengaturcaraan Dinamik, Percubaan
Anda diberikan rentetan 0-diindeks dan kamus perkataan kamus. Anda perlu memecahkan s kepada satu atau lebih tidak bertindih subrentetan supaya setiap subrentetan hadir dalam kamus. Mungkin terdapat beberapa aksara tambahan dalam s yang tidak terdapat dalam mana-mana subrentetan.
Kembalikan bilangan minimum aksara tambahan yang tinggal jika anda berpisah secara optimum.
Contoh 1:
- Input: s = "leetscode", kamus = ["leet","code","leetcode"]
- Output: 1
- Penjelasan: Kita boleh memecahkan s dalam dua subrentetan: "leet" dari indeks 0 hingga 3 dan "kod" dari indeks 5 hingga 8. Hanya ada 1 aksara yang tidak digunakan (pada indeks 4), jadi kami mengembalikan 1 .
Contoh 2:
- Input: s = "sayhelloworld", kamus = ["hello","world"]
- Output: 3
- Penjelasan: Kita boleh memecahkan s dalam dua subrentetan: "hello" dari indeks 3 hingga 7 dan "dunia" dari indeks 8 hingga 12. Aksara pada indeks 0, 1, 2 tidak digunakan dalam mana-mana subrentetan dan oleh itu dianggap sebagai watak tambahan. Oleh itu, kami kembalikan 3.
Kekangan:
- 1 <= s.panjang <= 50
- 1 <= kamus.panjang <= 50
- 1 <= kamus[i].panjang <= 50
- kamus[i] dan s hanya terdiri daripada huruf kecil Inggeris
- kamus mengandungi perkataan yang berbeza
Petunjuk:
- Bolehkah kita menggunakan Pengaturcaraan Dinamik di sini?
- Tentukan DP[i] sebagai aksara tambahan min jika putus s[0:i] secara optimum.
Penyelesaian:
Kita boleh menentukan tatasusunan dp dengan dp[i] mewakili bilangan minimum aksara tambahan dalam subrentetan s[0:i] selepas pembahagian optimum.
Pendekatan:
-
Definisi Pengaturcaraan Dinamik:
- Biar dp[i] sebagai bilangan minimum aksara tambahan dalam subrentetan s[0:i].
- Untuk mengira dp[i], kita boleh:
- Sama ada pertimbangkan watak s[i-1] sebagai watak tambahan dan beralih ke indeks seterusnya.
- Atau semak sama ada beberapa subrentetan yang berakhir dengan indeks i wujud dalam kamus, dan jika ya, gunakannya untuk mengurangkan aksara tambahan.
-
Peralihan:
- Untuk setiap indeks i, kita sama ada:
- Tambahkan satu pada dp[i-1] jika kita menganggap s[i] sebagai watak tambahan.
- Semak setiap kemungkinan subrentetan s[j:i] (untuk j < i) dan jika s[j:i] ada dalam kamus, kami mengemas kini dp[i] berdasarkan dp[j].
- Untuk setiap indeks i, kita sama ada:
-
Keputusan:
- Nilai dp[len(s)] akan memberi kita bilangan minimum aksara tambahan dalam keseluruhan rentetan s.
Mari laksanakan penyelesaian ini dalam PHP: 2707. Watak Tambahan dalam Rentetan
Penjelasan:
Kes Asas:
- dp[0] = 0 kerana tiada aksara tambahan wujud dalam rentetan kosong.
Cari Kamus:
- Kami menyimpan perkataan kamus dalam peta cincang menggunakan array_flip() untuk carian masa tetap.
Peralihan:
- Untuk setiap kedudukan i, kami menyemak semua kemungkinan subrentetan s[j:i]. Jika subrentetan wujud dalam kamus, kami mengemas kini nilai dp[i].
Kerumitan Masa:
- Kerumitan masa ialah O(n^2) dengan n ialah panjang rentetan s kerana bagi setiap indeks, kami menyemak semua indeks sebelumnya untuk membentuk subrentetan.
Keputusan Ujian:
Untuk input "leetscode" dengan kamus ["leet","code","leetcode"], fungsi ini mengembalikan 1 dengan betul, kerana hanya tinggal 1 aksara tambahan ("s").
Untuk input "sayhelloworld" dengan kamus ["hello","world"], fungsi mengembalikan 3, kerana tiga aksara pertama ("katakan") adalah tambahan.
Pautan Kenalan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!
Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:
- GitHub
Atas ialah kandungan terperinci Watak Tambahan dalam Rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

Video Face Swap
Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Artikel Panas

Alat panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas











JWT adalah standard terbuka berdasarkan JSON, yang digunakan untuk menghantar maklumat secara selamat antara pihak, terutamanya untuk pengesahan identiti dan pertukaran maklumat. 1. JWT terdiri daripada tiga bahagian: header, muatan dan tandatangan. 2. Prinsip kerja JWT termasuk tiga langkah: menjana JWT, mengesahkan JWT dan muatan parsing. 3. Apabila menggunakan JWT untuk pengesahan di PHP, JWT boleh dijana dan disahkan, dan peranan pengguna dan maklumat kebenaran boleh dimasukkan dalam penggunaan lanjutan. 4. Kesilapan umum termasuk kegagalan pengesahan tandatangan, tamat tempoh, dan muatan besar. Kemahiran penyahpepijatan termasuk menggunakan alat debugging dan pembalakan. 5. Pengoptimuman prestasi dan amalan terbaik termasuk menggunakan algoritma tandatangan yang sesuai, menetapkan tempoh kesahihan dengan munasabah,

Sesi rampasan boleh dicapai melalui langkah -langkah berikut: 1. Dapatkan ID Sesi, 2. Gunakan ID Sesi, 3. Simpan sesi aktif. Kaedah untuk mengelakkan rampasan sesi dalam PHP termasuk: 1. Gunakan fungsi Sesi_Regenerate_ID () untuk menjana semula ID Sesi, 2. Data sesi stor melalui pangkalan data, 3.

Prinsip reka bentuk Restapi termasuk definisi sumber, reka bentuk URI, penggunaan kaedah HTTP, penggunaan kod status, kawalan versi, dan benci. 1. Sumber harus diwakili oleh kata nama dan dikekalkan pada hierarki. 2. Kaedah HTTP harus mematuhi semantik mereka, seperti GET digunakan untuk mendapatkan sumber. 3. Kod status hendaklah digunakan dengan betul, seperti 404 bermakna sumber tidak wujud. 4. Kawalan versi boleh dilaksanakan melalui URI atau header. 5. Boots Operasi Pelanggan Hateoas melalui pautan sebagai tindak balas.

Dalam PHP, pengendalian pengecualian dicapai melalui percubaan, menangkap, akhirnya, dan membuang kata kunci. 1) blok percubaan mengelilingi kod yang boleh membuang pengecualian; 2) Blok tangkapan mengendalikan pengecualian; 3) Akhirnya Blok memastikan bahawa kod itu sentiasa dilaksanakan; 4) Lemparan digunakan untuk membuang pengecualian secara manual. Mekanisme ini membantu meningkatkan keteguhan dan mengekalkan kod anda.

Fungsi utama kelas tanpa nama dalam PHP adalah untuk membuat objek satu kali. 1. Kelas tanpa nama membenarkan kelas tanpa nama ditakrifkan secara langsung dalam kod, yang sesuai untuk keperluan sementara. 2. Mereka boleh mewarisi kelas atau melaksanakan antara muka untuk meningkatkan fleksibiliti. 3. Beri perhatian kepada prestasi dan kebolehbacaan kod apabila menggunakannya, dan elakkan berulang kali menentukan kelas tanpa nama yang sama.

Dalam PHP, perbezaan antara termasuk, memerlukan, termasuk_once, memerlukan_once adalah: 1) termasuk menghasilkan amaran dan terus melaksanakan, 2) memerlukan menghasilkan ralat maut dan berhenti pelaksanaan, 3) termasuk_once dan memerlukan_once mencegah kemasukan berulang. Pilihan fungsi ini bergantung kepada kepentingan fail dan sama ada perlu untuk mencegah kemasukan pendua. Penggunaan rasional dapat meningkatkan kebolehbacaan dan pemeliharaan kod.

Terdapat empat jenis kesilapan utama dalam PHP: 1.Notice: yang paling sedikit, tidak akan mengganggu program, seperti mengakses pembolehubah yang tidak ditentukan; 2. Amaran: Serius daripada notis, tidak akan menamatkan program, seperti tidak mengandungi fail; 3. FatalError: Yang paling serius, akan menamatkan program ini, seperti tidak memanggil fungsi; 4. ParseError: Kesalahan sintaks, akan menghalang program daripada dilaksanakan, seperti lupa untuk menambah tag akhir.

PHP dan Python masing -masing mempunyai kelebihan mereka sendiri, dan memilih mengikut keperluan projek. 1.PHP sesuai untuk pembangunan web, terutamanya untuk pembangunan pesat dan penyelenggaraan laman web. 2. Python sesuai untuk sains data, pembelajaran mesin dan kecerdasan buatan, dengan sintaks ringkas dan sesuai untuk pemula.
