. Tambah Minimum untuk Menjadikan Tanda Kurung Sah

921. Tambah Minimum untuk Menjadikan Tanda Kurung Sah

Kesukaran: Sederhana

Topik: Rentetan, Tindanan, Tamak

Rentetan kurungan sah jika dan hanya jika:

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

Anda diberi rentetan kurungan s. Dalam satu pergerakan, anda boleh memasukkan kurungan pada sebarang kedudukan rentetan.

• Sebagai contoh, jika s = "()))", anda boleh memasukkan kurungan pembuka menjadi "(()))" atau kurungan penutup menjadi "())))".

Kembali bilangan minimum pergerakan yang diperlukan untuk menjadikan s sah.

Contoh 1:

• Input: s = "())"
• Output: 1

Contoh 2:

• Input: s = "((("
• Output: 3

Kekangan:

• 1
• s[i] ialah sama ada '(' atau ')'.

Penyelesaian:

Kita perlu menentukan bilangan kurungan pembukaan atau penutup yang perlu ditambah untuk menjadikan rentetan input itu sah. Rentetan yang sah bermakna setiap kurungan pembukaan '(' mempunyai kurungan penutup yang sepadan ')'.

Kita boleh menyelesaikan masalah ini menggunakan pendekatan kaunter yang mudah:

• Kami menggunakan baki berubah untuk menjejaki baki semasa antara kurungan pembukaan dan penutup.
• Kami menggunakan penambahan pembolehubah lain untuk mengira bilangan kurungan minimum yang diperlukan.

Pendekatan:

1. Gelung melalui setiap aksara rentetan s.
2. Jika aksara ialah '(', naikkan baki sebanyak 1.
3. Jika aksara ialah ')', kurangkan baki sebanyak 1:
   • Jika baki menjadi negatif, ini bermakna terdapat lebih banyak kurungan penutup daripada kurungan pembukaan. Kita perlu menambah kurungan pembukaan untuk mengimbanginya, jadi tambahkan penambahan sebanyak 1 dan tetapkan semula baki kepada 0.
4. Di penghujung gelung, jika baki lebih besar daripada 0, ini menunjukkan terdapat kurungan bukaan yang tidak dapat dipadankan, jadi tambahkan baki pada penambahan.

Mari laksanakan penyelesaian ini dalam PHP: 921. Tambah Minimum untuk Menjadikan Tanda Kurung Sah

<?php /**
 * @param String $s
 * @return Integer
 */
function minAddToMakeValid($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$s1 = "())";
echo minAddToMakeValid($s1);  // Output: 1

$s2 = "(((";
echo minAddToMakeValid($s2);  // Output: 3
?>

Penjelasan:

• Untuk rentetan s = "())":
  • baki menjadi negatif apabila ')' kedua ditemui, jadi penambahan akan ditambah.
  • Pada akhirnya, baki ialah 0, dan penambahan ialah 1, jadi kita memerlukan 1 penambahan untuk menjadikan rentetan itu sah.
• Untuk rentetan s = "(((":
  • baki menjadi 3 kerana terdapat 3 '(' yang tidak sepadan di hujungnya.
  • Hasilnya ialah baki tambahan, iaitu 0 3 = 3.

Penyelesaian ini mempunyai kerumitan masa O(n) dengan n ialah panjang rentetan dan ruang kerumitan O(1) kerana kita hanya menggunakan beberapa pembolehubah.

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 . Tambah Minimum untuk Menjadikan Tanda Kurung Sah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!