Jadikan Rentetan Susunan Menggunakan Penambahan Kitaran

2825. Jadikan Rentetan Susunan Menggunakan Penambahan Kitaran

Kesukaran: Sederhana

Topik: Dua Penunjuk, Rentetan

Anda diberi dua 0-diindeks rentetan str1 dan str2.

Dalam operasi, anda memilih set indeks dalam str1, dan untuk setiap indeks i dalam set, naikkan str1[i] kepada aksara seterusnya secara kitaran. Iaitu 'a' menjadi 'b', 'b' menjadi 'c', dan seterusnya, dan 'z' menjadi 'a'.

Kembalikan benar jika boleh menjadikan str2 susulan str1 dengan melakukan operasi paling banyak sekali dan palsu sebaliknya.

Nota: Susunan rentetan ialah rentetan baharu yang terbentuk daripada rentetan asal dengan memadamkan beberapa (mungkin tiada) aksara tanpa mengganggu kedudukan relatif aksara yang tinggal.

Contoh 1:

• Input: str1 = "abc", str2 = "ad"
• Output: benar
• Penjelasan: Pilih indeks 2 dalam str1.
  • Naikkan str1[2] untuk menjadi 'd'.
  • Oleh itu, str1 menjadi "abd" dan str2 kini merupakan urutan. Oleh itu, benar dikembalikan.

Contoh 2:

• Input: str1 = "zc", str2 = "ad"
• Output: benar
• Penjelasan: Pilih indeks 0 dan 1 dalam str1.
  • Naikkan str1[0] untuk menjadi 'a'.
  • Naikkan str1[1] untuk menjadi 'd'.
  • Oleh itu, str1 menjadi "iklan" dan str2 kini merupakan urutan. Oleh itu, benar dikembalikan.

Contoh 3:

• Input: str1 = "ab", str2 = "d"
• Output: palsu
• Penjelasan: Dalam contoh ini, ia boleh ditunjukkan bahawa adalah mustahil untuk menjadikan str2 urutan str1 menggunakan operasi paling banyak sekali.
  • Oleh itu, palsu dikembalikan.

Kekangan:

• 1 <= str1.length <= 10⁵
• 1 <= str2.length <= 10⁵
• str1 dan str2 hanya terdiri daripada huruf kecil Inggeris.

Petunjuk:

1. Pertimbangkan indeks yang akan kami naikkan secara berasingan.
2. Kita boleh mengekalkan dua penunjuk: penunjuk i untuk str1 dan penunjuk j untuk str2, sambil memastikan ia kekal dalam sempadan rentetan.
3. Jika kedua-dua str1[i] dan str2[j] sepadan, atau jika penambahan str1[i] sepadan dengan str2[j], kami meningkatkan kedua-dua penunjuk; jika tidak, kami hanya menambah penunjuk i.
4. Adalah mungkin untuk menjadikan str2 susulan daripada str1 jika j berada di penghujung str2, selepas kita tidak dapat mencari padanan lagi.

Penyelesaian:

Kita perlu menyemak sama ada kita boleh menjadikan str2 urutan str1 dengan melakukan paling banyak satu operasi kenaikan kitaran pada mana-mana aksara dalam str1:

Penjelasan:

• Kami akan menggunakan dua penunjuk, i untuk str1 dan j untuk str2.
• Jika watak di str1[i] sepadan dengan str2[j], kami menggerakkan kedua-dua penunjuk ke hadapan.
• Jika str1[i] boleh dinaikkan untuk memadankan str2[j] (secara kitaran), kami cuba memadankannya dan kemudian menggerakkan kedua-dua penunjuk.
• Jika kedua-dua syarat di atas tidak berlaku, kami hanya menggerakkan penunjuk i untuk str1.
• Akhir sekali, jika kita boleh memadankan semua aksara str2, maka adalah mungkin untuk menjadikan str2 susulan daripada str1, jika tidak.

Mari laksanakan penyelesaian ini dalam PHP: 2825. Jadikan Rentetan Susulan Menggunakan Penambahan Kitaran

  
  
  Penjelasan:




Dua Penunjuk: i dan j dimulakan pada permulaan str1 dan str2, masing-masing.

Logik Pemadanan: Di dalam gelung, kami menyemak sama ada aksara di str1[i] dan str2[j] adalah sama atau jika kami boleh menambah str1[i] untuk memadankan str2[j] secara kitaran.


Keadaan kenaikan kitaran dikendalikan menggunakan (ord($str1[$i]) 1 - ord('a')) % 26 yang menyemak sama ada str1[i] boleh dinaikkan agar sepadan dengan str2[j].



Semakan Susulan: Jika kita telah melelar melalui str2 sepenuhnya (iaitu, j == m), ini bermakna str2 ialah susulan daripada str1. Jika tidak, tidak.



  
  
  Kerumitan Masa:



Algoritma berulang melalui str1 sekali, dan setiap aksara dalam str2 diperiksa sekali sahaja, jadi kerumitan masa ialah O(n), dengan n ialah panjang str1.



  
  
  Kerumitan Ruang:



Kerumitan ruang ialah O(1) kerana kami hanya menggunakan beberapa penunjuk dan tidak memerlukan ruang tambahan bergantung pada saiz input.


Penyelesaian ini dengan cekap memeriksa sama ada mungkin untuk menjadikan str2 urutan str1 dengan paling banyak satu operasi kenaikan kitaran.

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 Jadikan Rentetan Susunan Menggunakan Penambahan Kitaran. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!