Leetcode: Pembahagi Biasa Terhebat Rentetan

Pernyataan Masalah 1071. Pembahagi Sepunya Rentetan Terhebat

Untuk dua rentetan s dan t, kita sebut "t membahagi s" jika dan hanya jika s = t + t + t + ... + t + t (iaitu, t digabungkan dengan dirinya satu atau lebih kali).

Diberi dua rentetan str1 dan str2, kembalikan rentetan terbesar x supaya x membahagikan kedua-dua str1 dan str2.

Proses Pemikiran Saya

Walaupun leetcode menandakannya sebagai masalah Mudah, saya harus mengakui bahawa saya mendapati sukar untuk segera mencari penyelesaian.

Izinkan saya menyemak kes ujian yang disediakan oleh leetcode dan menyemaknya untuk menjelaskan kekeliruan saya.

Kes Ujian

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Daripada penyataan masalah dan kes ujian 1, saya telah menentukan bahawa kita perlu mengeluarkan rentetan terbesar("ABC") yang digabungkan yang kita boleh mendapatkan kedua-dua rentetan. (rentetan lalai "ABC" === str2 dan "ABC" + "ABC" === str1).

Walau bagaimanapun, melihat kes ujian 2 saya dengan cepat menyedari bahawa pemahaman saya tidak betul kerana menurutnya saya harus mengeluarkan "ABAB" kerana itu adalah rentetan terpanjang yang boleh saya gunakan untuk mencipta kedua-dua rentetan. Tetapi saya melompat ke kod dan mula memetakan penyelesaian. (Kesilapan orang baru?)

Apa yang Gagal/Berjaya

Saya hanya dapat memetakan penyelesaian di mana:

1. cari GCD bagi dua rentetan.
2. lelaran daripada panjang rentetan terkecil kepada GCD
3. ambil subrentetan daripada rentetan terkecil kepada nilai lelaran semasa.
4. jika kedua-dua rentetan mengandungi subrentetan itu kembalikan subrentetan itu sebagai jawapan.
5. jika tiada rentetan ditemui kembalikan "".

Seperti yang anda lihat penyelesaian saya gagal untuk rentetan di mana str1 mengandungi str2 tetapi juga mengandungi beberapa aksara tambahan lain. melanggar syarat bahawa s = t + t + ... + t + t.

Saya terpaksa beralih kepada penyelesaian neetcode untuk mendapatkan bantuan. Saya cepat memahami isu saya:

1. Saya sedang mencari GCD bagi panjang rentetan, BUKAN rentetan itu sendiri. Saya perlu mencari rentetan di mana mengulangi rentetan itu saya boleh mencipta kedua-dua rentetan tanpa sebarang aksara yang tinggal.

2. Saya sedar mengapa "ABAB" tidak boleh menjadi jawapan untuk kes ujian 2:

• kita perlu mencari x supaya ia membahagikan kedua-dua rentetan secara sama rata. jadi mengambil "ABAB" sebagai rentetan anda boleh mencipta str2 sepenuhnya tetapi untuk str1 anda berakhir dengan "ABABABAB". Anda mempunyai 2 lebihan "AB" dan tidak boleh mengatakan bahawa anda telah mencipta str1 sepenuhnya dengan menggabungkan x.

• "ABAB" panjang 4 dan "ABABAB" panjang 6. GCD 2 rentetan = 2. Oleh itu output perlu rentetan panjang 2.

Output

Kerumitan Masa dan Ruang

Kerumitan Masa:

Dalam kes yang paling teruk, kita melelang ke atas Min(str1,str2) dan kita perlu mencipta semula str1 dan str2 supaya menjadi (str1.length + str2.length) jadi masa keseluruhan kerumitan akan menjadi O(min(str1,str2) * (str1.length + str2.length))

Kerumitan Angkasa:

O(1) kerana kami tidak memerlukan sebarang ruang tambahan.

Atas ialah kandungan terperinci Leetcode: Pembahagi Biasa Terhebat Rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!