Persamaan Ayat III

1813. Persamaan Ayat III

Kesukaran: Sederhana

Topik: Tatasusunan, Dua Penunjuk, Rentetan

Anda diberi dua rentetan ayat1 dan ayat2, setiap satu mewakili ayat yang terdiri daripada perkataan. Ayat ialah senarai perkataan yang dipisahkan oleh ruang tunggal tanpa ruang hadapan atau belakang. Setiap perkataan hanya terdiri daripada huruf besar dan huruf kecil bahasa Inggeris.

Dua ayat s1 dan s2 dianggap serupa jika boleh memasukkan ayat arbitrari (kemungkinan kosong) di dalam salah satu ayat ini supaya kedua-dua ayat menjadi sama. Perhatikan bahawa ayat yang disisipkan mesti dipisahkan daripada perkataan sedia ada dengan ruang.

Sebagai contoh,

• s1 = "Hello Jane" dan s2 = "Hello my name is Jane" boleh dijadikan sama dengan memasukkan "my name is" antara "Hello" dan "Jane" dalam s1.
• s1 = "Frog cool" dan s2 = "Frogs are cool" tidak serupa, kerana walaupun terdapat ayat "s are" yang disisipkan ke dalam s1, ia tidak dipisahkan daripada "Frog" oleh ruang.

Diberi dua ayat ayat1 dan ayat2, kembalikan benar jika ayat1 dan ayat2 serupa. Jika tidak, kembalikan palsu.

Contoh 1:

• Input: sentence1 = "Nama saya Haley", ayat2 = "Haley Saya"
• Output: benar
• Penjelasan: ayat2 boleh ditukar kepada ayat1 dengan memasukkan "nama ialah" antara "Saya" dan "Haley".

Contoh 2:

• Input: ayat1 = "daripada", ayat2 = "Banyak perkataan"
• Output: palsu
• Penjelasan: Tiada ayat tunggal boleh disisipkan di dalam salah satu ayat untuk menjadikannya sama dengan yang lain.

Contoh 3:

• Input: sentence1 = "Makan sekarang", sentence2 = "Makan"
• Output: benar
• Penjelasan: ayat2 boleh ditukar kepada ayat1 dengan memasukkan "sekarang" di hujung ayat.

Kekangan:

• 1 <= ayat1.panjang, ayat2.panjang <= 100
• ayat1 dan ayat2 terdiri daripada huruf kecil dan huruf besar Inggeris dan ruang.
• Perkataan dalam ayat1 dan ayat2 dipisahkan oleh satu ruang.

Petunjuk:

1. Satu cara untuk melihatnya ialah mencari satu ayat sebagai gabungan awalan dan akhiran daripada ayat yang lain.
2. Dapatkan awalan sepunya terpanjang di antara mereka dan akhiran sepunya terpanjang.

Penyelesaian:

Kita boleh mendekatinya dengan membandingkan awalan biasa dan akhiran terpanjang kedua-dua ayat. Jika perkataan dalam bahagian baki satu ayat terkandung sepenuhnya dalam ayat lain (mungkin kosong), maka ayat tersebut boleh dianggap serupa.

Langkah-langkah:

1. Pisah kedua-dua ayat kepada tatasusunan perkataan.
2. Gunakan dua penunjuk untuk membandingkan awalan biasa terpanjang dari permulaan kedua-dua tatasusunan.
3. Gunakan dua penuding lagi untuk membandingkan akhiran biasa terpanjang dari penghujung kedua-dua tatasusunan.
4. Selepas membandingkan awalan dan akhiran biasa, jika baki perkataan dalam salah satu ayat membentuk tatasusunan kosong (bermaksud semuanya telah dipadankan), maka ayat tersebut dianggap serupa.

Mari laksanakan penyelesaian ini dalam PHP: 1813. Persamaan Ayat III

/**


@param String $sentence1
@param String $sentence2
@return Boolean
/
function areSentencesSimilar($sentence1, $sentence2) {
...
...
...
/*


go to ./solution.php
*/
}





// Test examples

$sentence1 = "My name is Haley";

$sentence2 = "My Haley";

echo areSentencesSimilar($sentence1, $sentence2) ? 'true' : 'false'; // Output: true

$sentence1 = "of";

$sentence2 = "A lot of words";

echo areSentencesSimilar($sentence1, $sentence2) ? 'true' : 'false'; // Output: false

$sentence1 = "Eating right now";

$sentence2 = "Eating";

echo areSentencesSimilar($sentence1, $sentence2) ? 'true' : 'false'; // Output: true

?>





  

  

  Penjelasan:





Memisahkan ayat menjadi perkataan: Kami menggunakan explode() untuk memisahkan rentetan ayat kepada tatasusunan perkataan.

Perbandingan awalan biasa: Kami mengulangi kedua-dua tatasusunan dari awal dan membandingkan perkataan yang sepadan. Gelung berterusan selagi perkataan sepadan.

Perbandingan akhiran biasa: Kami membandingkan perkataan dari hujung kedua-dua tatasusunan, sekali lagi menggunakan gelung untuk menyemak perkataan yang sepadan.

Semakan akhir: Selepas memproses awalan dan akhiran biasa, kami menyemak sama ada bilangan perkataan yang telah dipadankan (akhiran awalan) meliputi semua perkataan dalam ayat yang lebih pendek. Jika ya, ayat tersebut boleh dianggap serupa.



  
  
  Kerumitan Masa:



Kerumitan masa ialah O(n m), dengan n dan m ialah panjang ayat1 dan ayat2 masing-masing. Ini kerana kami memproses perkataan dalam kedua-dua ayat hanya sekali sambil menyemak awalan dan akhiran biasa.


Penyelesaian ini harus berfungsi dengan cekap memandangkan kekangan.

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 Persamaan Ayat III. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!