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:

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:




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:


LinkedIn
GitHub



          

            
  

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