Rumah pembangunan bahagian belakang tutorial php Watak Tambahan dalam Rentetan

Watak Tambahan dalam Rentetan

Sep 23, 2024 pm 04:16 PM

Extra Characters in a String

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:

  1. Bolehkah kita menggunakan Pengaturcaraan Dinamik di sini?
  2. 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:

  1. 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.
  2. 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].
  3. 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:

  1. Kes Asas:

    • dp[0] = 0 kerana tiada aksara tambahan wujud dalam rentetan kosong.
  2. Cari Kamus:

    • Kami menyimpan perkataan kamus dalam peta cincang menggunakan array_flip() untuk carian masa tetap.
  3. Peralihan:

    • Untuk setiap kedudukan i, kami menyemak semua kemungkinan subrentetan s[j:i]. Jika subrentetan wujud dalam kamus, kami mengemas kini nilai dp[i].
  4. 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:

  • LinkedIn
  • GitHub

Atas ialah kandungan terperinci Watak Tambahan dalam Rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Video Face Swap

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

Artikel Panas

<🎜>: Bubble Gum Simulator Infinity - Cara Mendapatkan dan Menggunakan Kekunci Diraja
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Nordhold: Sistem Fusion, dijelaskan
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Whispers of the Witch Tree - Cara Membuka Kunci Cangkuk Bergelut
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Tutorial Java
1672
14
Tutorial PHP
1276
29
Tutorial C#
1256
24
Terangkan hashing kata laluan yang selamat di PHP (mis., Password_hash, password_verify). Mengapa tidak menggunakan MD5 atau SHA1? Terangkan hashing kata laluan yang selamat di PHP (mis., Password_hash, password_verify). Mengapa tidak menggunakan MD5 atau SHA1? Apr 17, 2025 am 12:06 AM

Dalam php, kata laluan_hash dan kata laluan 1) password_hash menjana hash yang mengandungi nilai garam untuk meningkatkan keselamatan. 2) Kata Laluan_verify Sahkan kata laluan dan pastikan keselamatan dengan membandingkan nilai hash. 3) MD5 dan SHA1 terdedah dan kekurangan nilai garam, dan tidak sesuai untuk keselamatan kata laluan moden.

PHP dan Python: Membandingkan dua bahasa pengaturcaraan yang popular PHP dan Python: Membandingkan dua bahasa pengaturcaraan yang popular Apr 14, 2025 am 12:13 AM

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.

PHP dalam Tindakan: Contoh dan aplikasi dunia nyata PHP dalam Tindakan: Contoh dan aplikasi dunia nyata Apr 14, 2025 am 12:19 AM

PHP digunakan secara meluas dalam e-dagang, sistem pengurusan kandungan dan pembangunan API. 1) e-dagang: Digunakan untuk fungsi keranjang belanja dan pemprosesan pembayaran. 2) Sistem Pengurusan Kandungan: Digunakan untuk penjanaan kandungan dinamik dan pengurusan pengguna. 3) Pembangunan API: Digunakan untuk Pembangunan API RESTful dan Keselamatan API. Melalui pengoptimuman prestasi dan amalan terbaik, kecekapan dan pemeliharaan aplikasi PHP bertambah baik.

Bagaimanakah jenis membayangkan jenis PHP, termasuk jenis skalar, jenis pulangan, jenis kesatuan, dan jenis yang boleh dibatalkan? Bagaimanakah jenis membayangkan jenis PHP, termasuk jenis skalar, jenis pulangan, jenis kesatuan, dan jenis yang boleh dibatalkan? Apr 17, 2025 am 12:25 AM

Jenis PHP meminta untuk meningkatkan kualiti kod dan kebolehbacaan. 1) Petua Jenis Skalar: Oleh kerana Php7.0, jenis data asas dibenarkan untuk ditentukan dalam parameter fungsi, seperti INT, Float, dan lain -lain. 2) Return Type Prompt: Pastikan konsistensi jenis nilai pulangan fungsi. 3) Jenis Kesatuan Prompt: Oleh kerana Php8.0, pelbagai jenis dibenarkan untuk ditentukan dalam parameter fungsi atau nilai pulangan. 4) Prompt jenis yang boleh dibatalkan: membolehkan untuk memasukkan nilai null dan mengendalikan fungsi yang boleh mengembalikan nilai null.

Relevannya PHP: Adakah ia masih hidup? Relevannya PHP: Adakah ia masih hidup? Apr 14, 2025 am 12:12 AM

PHP masih dinamik dan masih menduduki kedudukan penting dalam bidang pengaturcaraan moden. 1) kesederhanaan PHP dan sokongan komuniti yang kuat menjadikannya digunakan secara meluas dalam pembangunan web; 2) fleksibiliti dan kestabilannya menjadikannya cemerlang dalam mengendalikan borang web, operasi pangkalan data dan pemprosesan fail; 3) PHP sentiasa berkembang dan mengoptimumkan, sesuai untuk pemula dan pemaju yang berpengalaman.

PHP dan Python: Paradigma yang berbeza dijelaskan PHP dan Python: Paradigma yang berbeza dijelaskan Apr 18, 2025 am 12:26 AM

PHP terutamanya pengaturcaraan prosedur, tetapi juga menyokong pengaturcaraan berorientasikan objek (OOP); Python menyokong pelbagai paradigma, termasuk pengaturcaraan OOP, fungsional dan prosedur. PHP sesuai untuk pembangunan web, dan Python sesuai untuk pelbagai aplikasi seperti analisis data dan pembelajaran mesin.

Bagaimana anda menghalang suntikan SQL di PHP? (Penyataan yang disediakan, PDO) Bagaimana anda menghalang suntikan SQL di PHP? (Penyataan yang disediakan, PDO) Apr 15, 2025 am 12:15 AM

Menggunakan penyataan preprocessing dan PDO dalam PHP secara berkesan dapat mencegah serangan suntikan SQL. 1) Gunakan PDO untuk menyambung ke pangkalan data dan tetapkan mod ralat. 2) Buat kenyataan pra -proses melalui kaedah menyediakan dan lulus data menggunakan ruang letak dan laksanakan kaedah. 3) Hasil pertanyaan proses dan pastikan keselamatan dan prestasi kod.

PHP dan Python: Contoh dan perbandingan kod PHP dan Python: Contoh dan perbandingan kod Apr 15, 2025 am 12:07 AM

PHP dan Python mempunyai kelebihan dan kekurangan mereka sendiri, dan pilihannya bergantung kepada keperluan projek dan keutamaan peribadi. 1.PHP sesuai untuk pembangunan pesat dan penyelenggaraan aplikasi web berskala besar. 2. Python menguasai bidang sains data dan pembelajaran mesin.

See all articles