Cari Panjang Awalan Biasa Terpanjang

3043. Cari Panjang Awalan Biasa Terpanjang

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Rentetan, Percubaan

Anda diberi dua tatasusunan dengan positif integer arr1 dan arr2.

A awalan integer positif ialah integer yang dibentuk oleh satu atau lebih digitnya, bermula daripada digit paling kirinya. Contohnya, 123 ialah awalan bagi integer 12345, manakala 234 ialah bukan.

A awalan biasa daripada dua integer a dan b ialah integer c, sehingga c ialah awalan bagi kedua-dua a dan b. Contohnya, 5655359 dan 56554 mempunyai awalan biasa 565 manakala 1223 dan 43456 tidak mempunyai awalan biasa.

Anda perlu mencari panjang awalan sepunya terpanjang antara semua pasangan integer (x, y) supaya x tergolong dalam arr1 dan y tergolong dalam arr2.

Kembalikan panjang terpanjang awalan biasa antara semua pasangan. Jika tiada awalan biasa wujud di kalangan mereka, kembalikan 0.

Contoh 1:

• Input: arr1 = [1,10,100], arr2 = [1000]
• Output: 3
• Penjelasan: Terdapat 3 pasangan (arr1[i], arr2[j]):
  • Awalan sepunya terpanjang bagi (1, 1000) ialah 1.
  • Awalan biasa terpanjang bagi (10, 1000) ialah 10.
  • Awalan biasa terpanjang bagi (100, 1000) ialah 100.
  • Awalan biasa terpanjang ialah 100 dengan panjang 3.

Contoh 2:

• Input: arr1 = [1,2,3], arr2 = [4,4,4]
• Output: 4
• Penjelasan: Tiada awalan sepunya untuk mana-mana pasangan (arr1[i], arr2[j]), maka kami mengembalikan 0.
  • Perhatikan bahawa awalan biasa antara elemen tatasusunan yang sama tidak dikira.

Kekangan:

• 1 <= arr1.length, arr2.length <= 5 * 10⁴
• 1 <= arr1[i], arr2[i] <= 10⁸

Petunjuk:

1. Letakkan semua kemungkinan awalan setiap elemen dalam arr1 ke dalam HashSet.
2. Untuk semua kemungkinan awalan setiap elemen dalam arr2, semak sama ada ia wujud dalam HashSet.

Penyelesaian:

Kami boleh menggunakan HashSet untuk menyimpan awalan daripada satu tatasusunan dan kemudian semak awalan tersebut dalam tatasusunan kedua.

Pendekatan:

1. Jana Awalan: Untuk setiap nombor dalam arr1 dan arr2, jana semua awalan yang mungkin. Awalan dibentuk oleh satu atau lebih digit bermula dari digit paling kiri.

2. Simpan Awalan arr1 dalam Set: Menggunakan HashSet untuk menyimpan semua awalan nombor dalam arr1 memastikan carian pantas apabila menyemak awalan daripada arr2.

3. Cari Awalan Biasa Terpanjang: Untuk setiap nombor dalam arr2, hasilkan awalannya dan semak sama ada mana-mana awalan ini wujud dalam HashSet dari langkah 2. Jejaki awalan terpanjang ditemui.

4. Kembalikan Panjang Awalan Biasa Terpanjang: Jika awalan biasa ditemui, kembalikan panjangnya; jika tidak, kembalikan 0.

Mari laksanakan penyelesaian ini dalam PHP: 3043. Cari Panjang Awalan Biasa Terpanjang

  
  
  Penjelasan:




Penciptaan HashSet:


Kami mula-mula mencipta tatasusunan bersekutu $prefixSet untuk menahan semua kemungkinan awalan nombor dalam arr1.
Kami mengulangi setiap nombor dalam arr1, menukarnya kepada rentetan dan mengekstrak semua awalannya menggunakan fungsi substr. Setiap awalan disimpan dalam $prefixSet.



Semakan Awalan:


Seterusnya, kami mengulangi setiap nombor dalam arr2, menukarnya kepada rentetan juga.
Untuk setiap nombor dalam arr2, kami sekali lagi mengeluarkan semua kemungkinan awalan.
Jika awalan wujud dalam $prefixSet, kami menyemak sama ada panjangnya lebih besar daripada panjang maksimum semasa yang ditemui ($maxLength).



Kembalikan Keputusan:


Akhir sekali, kami mengembalikan panjang awalan biasa terpanjang yang ditemui.





  
  
  Kerumitan:




Kerumitan Masa: O(n * m) dengan n dan m ialah panjang arr1 dan arr2 masing-masing. Ini kerana kami sedang memproses setiap nombor dan awalan mereka.

Kerumitan Ruang: O(p) dengan p ialah jumlah bilangan awalan yang disimpan dalam HashSet.


Penyelesaian ini cekap dan berfungsi dengan baik dalam kekangan yang disediakan.

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 Cari Panjang Awalan Biasa Terpanjang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!