Pisahkan Rentetan Kepada Bilangan Maksimum Subrentetan Unik

1593. Pisahkan Rentetan Kepada Bilangan Maksimum Subrentetan Unik

Kesukaran: Sederhana

Topik: Jadual Hash, Rentetan, Menjejak Belakang

Memandangkan rentetan s, kembalikan bilangan maksimum subrentetan unik yang rentetan yang diberikan boleh dipecah menjadi.

Anda boleh membahagikan rentetan s kepada mana-mana senarai subrentetan bukan kosong, di mana gabungan subrentetan itu membentuk rentetan asal. Walau bagaimanapun, anda mesti membahagikan subrentetan supaya kesemuanya unik.

subrentetan ialah jujukan aksara bersebelahan dalam rentetan.

Contoh 1:

• Input: s = "ababccc"
• Output: 5
• Penjelasan: Satu cara untuk membelah secara maksimum ialah ['a', 'b', 'ab', 'c', 'cc']. Pemisahan seperti ['a', 'b', 'a', 'b', 'c', 'cc'] tidak sah kerana anda mempunyai 'a' dan 'b' beberapa kali.

Contoh 2:

• Input: s = "aba"
• Output: 2
• Penjelasan: Satu cara untuk berpecah secara maksimum ialah ['a', 'ba'].

Contoh 3:

• Input: s = "aa"
• Output: 1
• Penjelasan: Tidak mustahil untuk memisahkan rentetan lebih jauh.

Kekangan:

• 1
• s hanya mengandungi huruf kecil Inggeris.

Petunjuk:

1. Gunakan set untuk menjejaki subrentetan yang telah digunakan
2. Cuba setiap subrentetan yang mungkin pada setiap kedudukan dan undur jika pemisahan lengkap tidak dapat dilakukan

Penyelesaian:

Kita boleh menggunakan pendekatan menjejak ke belakang. Ini melibatkan percubaan secara rekursif untuk mencipta subrentetan daripada kedudukan semasa dalam rentetan dan menjejaki subrentetan unik yang telah kami gunakan setakat ini.

Berikut ialah penyelesaian langkah demi langkah:

1. Fungsi Rekursif: Buat fungsi yang akan meneroka semua subrentetan yang mungkin bermula daripada indeks semasa rentetan.
2. Tetapkan untuk Keunikan: Gunakan set (atau tatasusunan dalam PHP) untuk menjejaki subrentetan unik yang telah digunakan dalam laluan rekursi semasa.
3. Penjejakan Belakang: Apabila subrentetan dipilih, kita boleh terus memilih subrentetan seterusnya. Jika kita mencapai titik di mana tiada subrentetan lagi boleh dibentuk tanpa berulang, kita mundur.
4. Kes Asas: Jika kita mencapai penghujung rentetan, kita mengira subrentetan unik yang terbentuk.

Mari laksanakan penyelesaian ini dalam PHP: 1593. Pisahkan Rentetan Kepada Bilangan Maksimum Subrentetan Unik

<?php class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function maxUniqueSplit($s) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $s
     * @param $used
     * @param $start
     * @return int|mixed
     */
    private function backtrack($s, $used, $start) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage
$solution = new Solution();
echo $solution->maxUniqueSplit("ababccc"); // Output: 5
echo "\n";
echo $solution->maxUniqueSplit("aba"); // Output: 2
echo "\n";
echo $solution->maxUniqueSplit("aa"); // Output: 1
?>

Penjelasan:

1. Tandatangan Fungsi: Fungsi utama ialah maxUniqueSplit, yang memulakan proses menjejak ke belakang.

2. Menjejak ke belakang:

   • Fungsi backtrack mengambil rentetan, tatasusunan subrentetan terpakai dan indeks permulaan semasa.
   • Jika indeks permulaan mencapai penghujung rentetan, ia mengembalikan kiraan subrentetan unik yang dikumpul.
   • Gelung berulang melalui kemungkinan indeks akhir untuk mencipta subrentetan daripada indeks permulaan.
   • Jika subrentetan itu unik (belum berada dalam tatasusunan terpakai), ia ditambahkan pada terpakai dan fungsi itu berulang untuk indeks seterusnya.
   • Selepas meneroka laluan itu, ia mengalih keluar subrentetan untuk berundur dan meneroka kemungkinan lain.

3. Output: Fungsi mengembalikan bilangan maksimum subrentetan unik untuk pelbagai rentetan input.

Kerumitan

• Kerumitan masa boleh menjadi tinggi disebabkan sifat menjejak ke belakang, terutamanya untuk rentetan yang lebih panjang, tetapi memandangkan kekangan (panjang maksimum 16), penyelesaian ini cukup cekap untuk had input.

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 Pisahkan Rentetan Kepada Bilangan Maksimum Subrentetan Unik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!