Semak sama ada Rentetan Tanda Kurung Boleh Sah

2116. Semak sama ada Rentetan Tanda Kurung Boleh Sah

Kesukaran: Sederhana

Topik: Rentetan, Tindanan, Tamak

Rentetan kurungan ialah rentetan bukan kosong yang hanya terdiri daripada '(' dan ')'. Ia sah jika mana-mana syarat berikut adalah benar:

• Ia adalah ().
• Ia boleh ditulis sebagai AB (A bercantum dengan B), dengan A dan B ialah rentetan kurungan yang sah.
• Ia boleh ditulis sebagai (A), dengan A ialah rentetan kurungan yang sah.

Anda diberi rentetan kurungan s dan rentetan dikunci, kedua-duanya panjang n. dikunci ialah rentetan binari yang hanya terdiri daripada '0' dan '1's. Untuk setiap indeks i terkunci,

• Jika dikunci[i] ialah '1', anda tidak boleh menukar s[i].
• Tetapi jika dikunci[i] ialah '0', anda boleh menukar s[i] kepada sama ada '(' atau ')'.

Kembali benar jika anda boleh membuat s rentetan kurungan yang sah. Jika tidak, pulangkan palsu.

Contoh 1:

• Input: s = "))()))", dikunci = "010100"
• Output: benar
• Penjelasan: dikunci[1] == '1' dan dikunci[3] == '1', jadi kami tidak boleh menukar s[1] atau s[3].
  • Kami menukar s[0] dan s[4] kepada '(' sambil membiarkan s[2] dan s[5] tidak berubah untuk menjadikan s sah.

Contoh 2:

• Input: s = "()()", dikunci = "0000"
• Output: benar
• Penjelasan: Kami tidak perlu membuat sebarang perubahan kerana s sudah sah.

Contoh 3:

• Input: s = ")", dikunci = "0"
• Output: palsu
• Penjelasan: dikunci membenarkan kami menukar s[0].
  • Menukar s[0] kepada sama ada '(' atau ')' tidak akan menjadikan s sah.

Kekangan:

• n == s.panjang == dikunci.panjang
• 1 5
• s[i] ialah sama ada '(' atau ')'.
• dikunci[i] sama ada '0' atau '1'.

Petunjuk:

1. Bolehkah rentetan panjang ganjil sah?
2. Dari kiri ke kanan, jika ')' terkunci ditemui, ia mesti seimbang dengan sama ada '(' berkunci atau indeks tidak berkunci di sebelah kirinya. Jika kedua-duanya tidak wujud, apakah kesimpulan yang boleh dibuat? Jika kedua-duanya wujud, yang manakah lebih disukai untuk digunakan?
3. Selepas perkara di atas, kami mungkin telah mengunci indeks '(' dan indeks tambahan tidak berkunci. Bagaimanakah anda boleh mengimbangi '(' yang terkunci sekarang? Bagaimana jika anda tidak dapat mengimbangi mana-mana '(' yang terkunci?

Penyelesaian:

Kita boleh mendekatinya langkah demi langkah, mengingati kekangan dan tingkah laku kedudukan terkunci.

Perkara Utama:

1. Jika panjang rentetan itu ganjil, kita boleh segera mengembalikan palsu kerana rentetan kurungan yang sah mesti mempunyai panjang genap (setiap bukaan ( memerlukan penutup )).
2. Kita perlu menjejaki bilangan kurungan terbuka (() dan kurungan tertutup ()) semasa kita mengulangi rentetan itu. Jika pada bila-bila masa bilangan kurungan penutup melebihi bilangan kurungan pembukaan, adalah mustahil untuk mengimbangi rentetan dan kami mengembalikan palsu.
3. Kita mesti berhati-hati mengendalikan kedudukan yang dikunci (dikunci[i] == '1') dan tidak dikunci (dikunci[i] == '0'). Kedudukan yang tidak dikunci membolehkan kita menukar watak, tetapi kedudukan yang dikunci tidak.

Algoritma:

• Langkah 1: Periksa sama ada panjang rentetan s adalah ganjil. Jika ya, balas palsu segera.
• Langkah 2: Gelung melalui rentetan dari kiri ke kanan untuk menjejaki baki kurungan.
  • Gunakan pembilang untuk menjejaki keseimbangan antara tanda kurung buka (dan tutup).
  • Jika pada bila-bila masa, bilangan kurungan penutup melebihi kurungan pembukaan, periksa sama ada kedudukan terkunci mempunyai fleksibiliti yang mencukupi untuk mengimbanginya.
  • Selepas memproses keseluruhan rentetan, periksa sama ada kurungan adalah seimbang, iaitu, jika tiada kurungan pembuka yang tidak dapat dipadankan.

Mari laksanakan penyelesaian ini dalam PHP: 2116. Semak sama ada Rentetan Tanda Kurung Boleh Sah

<?php /**
 * @param String $s
 * @param String $locked
 * @return Boolean
 */
function canBeValid($s, $locked) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$s = "))()))";
$locked = "010100";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = "()()";
$locked = "0000";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = ")";
$locked = "0";
var_dump(canBeValid($s, $locked));  // Output: bool(false)
?>

Penjelasan:

1. Hantaran pertama (kiri ke kanan):

   • Kami mengulangi rentetan dan menjejaki baki kurungan terbuka. Setiap kali kami menghadapi kurungan terbuka (, kami menambah pembilang terbuka. Untuk kurungan tertutup ), kami mengurangkan pembilang terbuka.
   • Jika aksara semasa tidak dikunci (dikunci[i] == '0'), kita boleh menganggapnya sebagai (jika perlu untuk mengimbangi kurungan.
   • Jika pada bila-bila masa pembilang terbuka menjadi negatif, ini bermakna kita mempunyai lebih banyak kurungan penutup daripada pembuka, dan kita membalas palsu.

2. Hantaran kedua (kanan ke kiri):

   • Kami melakukan operasi yang serupa secara terbalik untuk mengendalikan senario kurungan pembukaan yang tidak dapat dipadankan yang mungkin berada di hujung rentetan.
   • Di sini kami menjejaki kurungan tutup ()) dengan kaunter tutup dan memastikan tiada kurungan tidak seimbang wujud.

3. Kes Tepi: Jika panjang rentetan adalah ganjil, kami segera mengembalikan palsu kerana ia tidak boleh membentuk rentetan kurungan yang sah.

Kerumitan Masa:

• Kedua-dua hantaran (kiri-ke-kanan dan kanan-ke-kiri) mengambil masa linear, O(n), dengan n ialah panjang rentetan. Oleh itu, kerumitan masa keseluruhan ialah O(n), yang cekap untuk kekangan saiz input.

Penyelesaian ini menangani masalah dengan betul dalam kekangan yang diberikan.

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 Semak sama ada Rentetan Tanda Kurung Boleh Sah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!