Gerakkan Kepingan untuk Mendapatkan Rentetan

2337. Gerakkan Kepingan untuk Mendapatkan Rentetan

Kesukaran: Sederhana

Topik: Dua Penunjuk, Rentetan

Anda diberi dua rentetan permulaan dan sasaran, kedua-duanya panjang n. Setiap rentetan hanya terdiri daripada aksara 'L', 'R' dan '_' di mana:

• Aksara 'L' dan 'R' mewakili kepingan, di mana sekeping 'L' boleh bergerak ke kiri hanya jika terdapat ruang kosong terus ke kirinya, dan sekeping 'R' boleh bergerak ke kanan hanya jika terdapat ruang kosong terus ke betul.
• Watak '_' mewakili ruang kosong yang boleh diduduki oleh mana-mana bahagian 'L' atau 'R'.

Kembali benar jika mungkin untuk mendapatkan sasaran rentetan dengan menggerakkan kepingan rentetan bermula beberapa kali. Jika tidak, pulangkan palsu.

Contoh 1:

• Input: mula = "LRR", sasaran = "L______RR"
• Output: benar
• Penjelasan: Kita boleh mendapatkan sasaran rentetan dari awal dengan melakukan langkah berikut:
  • Alihkan bahagian pertama satu langkah ke kiri, mula menjadi sama dengan "L__RR".
  • Alihkan bahagian terakhir satu langkah ke kanan, mula menjadi sama dengan "L_R_R".
  • Alihkan bahagian kedua tiga langkah ke kanan, mula menjadi sama dengan "L______RR".
  • Memandangkan adalah mungkin untuk mendapatkan sasaran rentetan dari awal, kami kembali benar.

Contoh 2:

• Input: mula = "R_L_", sasaran = "__LR"
• Output: palsu
• Penjelasan: Sekeping 'R' dalam permulaan rentetan boleh bergerak satu langkah ke kanan untuk mendapatkan "RL".
  • Selepas itu, tiada kepingan boleh bergerak lagi, jadi adalah mustahil untuk mendapatkan sasaran rentetan dari awal.

Contoh 3:

• Input: mula = "R", sasaran = "R"
• Output: palsu
• Output: Potongan dalam permulaan rentetan boleh bergerak hanya ke kanan, jadi adalah mustahil untuk mendapatkan sasaran rentetan dari mula.

Kekangan:

• n == mula.panjang == sasaran.panjang
• 1 <= n <= 10⁵
• permulaan dan sasaran terdiri daripada aksara 'L', 'R' dan '_'.

Petunjuk:

1. Selepas beberapa urutan pergerakan, bolehkah susunan kepingan berubah?
2. Cuba padankan setiap bahagian dalam s dengan sekeping dalam e.

Penyelesaian:

Kita perlu menyemak sama ada kita boleh mengubah permulaan rentetan menjadi sasaran rentetan dengan menggerakkan kepingan ('L' dan 'R') mengikut peraturan yang diberikan. Kekangan utama yang perlu dipertimbangkan ialah:

• 'L' hanya boleh bergerak ke kiri (dan tidak boleh melintasi kepingan 'L' atau 'R' yang lain).
• 'R' hanya boleh bergerak ke kanan (dan tidak boleh melintasi kepingan 'L' atau 'R' yang lain).
• Kita boleh menggunakan mana-mana ruang kosong ('_') untuk mengalihkan kepingan.

Pelan:

1. Semak Panjang: Mula-mula, semak sama ada kedua-dua rentetan mempunyai panjang yang sama. Jika tidak, balas palsu segera.

2. Semakan Kekerapan Watak: Bilangan 'L's, 'R's, dan '_' dalam rentetan permulaan mesti sepadan dengan kiraan masing-masing dalam rentetan sasaran kerana kepingan tidak boleh diduplikasi atau dimusnahkan , hanya berpindah.

3. Padanan Sekeping Menggunakan Dua Penunjuk:

   • Melintasi kedua-dua rentetan (mula dan sasaran).
   • Periksa sama ada setiap bahagian ('L' atau 'R') pada permulaan boleh bergerak ke kedudukan yang sepadan dalam sasaran.
   • Khususnya:
     • 'L' hendaklah sentiasa bergerak ke kiri (iaitu, ia mestilah tidak berada dalam kedudukan di mana bahagian dalam sasaran harus bergerak ke kanan).
     • 'R' hendaklah sentiasa bergerak ke kanan (iaitu, ia mestilah tidak berada dalam kedudukan di mana bahagian dalam sasaran harus bergerak ke kiri).

Penjelasan Algoritma:

1. Penapis Kedudukan L dan R:

   • Alih keluar semua _ daripada kedua-dua rentetan permulaan dan sasarkan untuk membandingkan jujukan L dan R. Jika jujukan berbeza, kembalikan palsu dengan segera.

2. Perjalanan Dua Mata:

   • Gunakan dua penunjuk untuk mengulangi aksara dalam permulaan dan sasaran.
   • Pastikan bahawa:
     • Untuk L, kepingan di permulaan hanya boleh bergerak kiri, jadi kedudukannya di permulaan hendaklah lebih besar daripada atau sama dengan kedudukannya dalam sasaran.
     • Untuk R, kepingan di permulaan hanya boleh bergerak kanan, jadi kedudukannya di permulaan hendaklah kurang daripada atau sama dengan kedudukannya dalam sasaran.

3. Hasil Output:

   • Jika semua syarat dipenuhi semasa traversal, kembalikan benar. Jika tidak, pulangkan palsu.

Mari laksanakan penyelesaian ini dalam PHP: 2337. Gerakkan Kepingan untuk Mendapatkan Rentetan

  
  
  Penjelasan:



Semakan Awal: Mula-mula, kami menyemak panjang kedua-dua rentetan dan memastikan kiraan 'L' dan 'R' adalah sama dalam kedua-dua rentetan. Jika tidak, balas palsu.

Logik Dua Penunjuk: Kami menggunakan dua penunjuk, i dan j, untuk melintasi kedua-dua rentetan:

Langkau ke atas ruang kosong ('_') kerana ia tidak menjejaskan pergerakan kepingan.
Jika aksara di i dan j dalam permulaan dan sasaran berbeza, kembalikan palsu (kerana kami tidak boleh mengalihkan kepingan ke aksara yang berbeza).
Jika 'L' ditemui pada permulaan dan berada pada kedudukan yang lebih besar daripada kedudukan sasarannya, atau jika 'R' ditemui pada permulaan dan berada pada kedudukan yang lebih kecil daripada kedudukan sasarannya, kembalikan palsu (sejak 'L ' hanya boleh bergerak ke kiri dan 'R' hanya boleh bergerak ke kanan).



Kes Tepi: Penyelesaian mengendalikan semua kes tepi yang mungkin, seperti:


Bilangan berbeza 'L' atau 'R' dalam permulaan dan sasaran.
Ketidakupayaan untuk memindahkan kepingan kerana kekangan.





  
  
  Kerumitan Masa:



Kerumitan masa ialah O(n), dengan n ialah panjang rentetan input. Ini kerana kami melintasi setiap rentetan sekali sahaja.



  
  
  Kerumitan Ruang:



Kerumitan ruang ialah O(1), kerana kami hanya menggunakan jumlah ruang tambahan yang tetap.



  
  
  Analisis Kerumitan:




Kerumitan Masa:


Menapis garis bawah mengambil masa O(n).
Perjalanan dua mata mengambil masa O(n).
Keseluruhan: O(n).



Kerumitan Angkasa:


Dua rentetan ($startNoUnderscore dan $targetNoUnderscore) dicipta, setiap satu bersaiz O(n).
Keseluruhan: O(n).





  
  
  Penjelasan Kes Ujian:




Input: _L__R__R_, L______RR


Jujukan padanan L dan R.
Setiap bahagian boleh dialihkan ke kedudukan yang diperlukan mengikut peraturan.

Output: benar.



Input: R_L_, __LR


Jujukan padanan L dan R.
Sekeping R tidak boleh bergerak ke kiri; oleh itu, transformasi adalah mustahil.

Output: palsu.



Input: _R, R_


Sekeping R tidak boleh bergerak ke kiri; oleh itu, transformasi adalah mustahil.

Output: palsu.




Pelaksanaan ini cekap dan mematuhi kekangan masalah, menjadikannya sesuai untuk saiz input yang besar.

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 Gerakkan Kepingan untuk Mendapatkan Rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!