Valid Parentheses

Q: Berapa kompleksitas waktu dari Valid Parentheses?

Solusi stack berjalan dalam waktu O(n) , karena setiap karakter didorong atau dikeluarkan paling banyak satu kali. Dalam kasus terburuk, solusi ini menggunakan ruang O(n) , yaitu untuk string yang hanya berisi tanda kurung pembuka. Menghapus pasangan yang cocok berulang kali membutuhkan waktu O(n²) , karena string bertingkat dalam hanya kehilangan satu pasangan pada setiap putaran.

MudahStack

+10

Kamu mendapatkan string s yang hanya terdiri dari karakter tanda kurung (, ), [, ], {, dan }. Kembalikan true jika tanda kurungnya seimbang: setiap tanda kurung penutup menutup tanda kurung terbaru yang masih terbuka, keduanya harus sejenis, dan tidak ada tanda kurung yang tersisa terbuka di akhir. Jika tidak, kembalikan false.

Fungsi

isValid(s: string) → boolean

sstring: string tanda kurung yang akan diperiksa
Mengembalikanboolean: apakah tanda kurungnya seimbang

Batasan

1 ≤ s.length ≤ 10⁴
s hanya berisi karakter (, ), [, ], {, dan }.

Contoh

Input: s = "[]{}()"
Output: true
Penjelasan: Tiga pasang berdiri berdampingan, dan masing-masing menutup tepat setelah dibuka.

Input: s = "{(})"
Output: false
Penjelasan: } muncul saat ( yang dibuka setelahnya masih terbuka, jadi tanda kurung itu menutup jenis tanda kurung yang salah.

Pertanyaan lanjutan

Jika string hanya berisi tanda kurung biasa, bisakah kamu memeriksanya dengan satu penghitung, bukan stack, dengan ruang tambahan O(1)?

Solusi

Menghitung tanda kurung saja tidak cukup: {(}) memiliki masing-masing satu tanda pembuka dan penutup, tetapi tetap salah karena urutannya penting. Stack menyimpan tanda kurung yang masih terbuka sesuai urutan saat dibuka, sehingga satu kali pemindaian dengan stack bisa menentukan apakah seluruh string valid.

Menghapus pasangan yang cocok berulang kali

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Setiap string seimbang memiliki sepasang kurung paling dalam tanpa apa pun di antaranya, seperti () di dalam {[()]}. Menghapus pasangan berdekatan yang cocok tidak pernah mengubah apakah sebuah string seimbang. Jadi, ulangi penghapusan sampai tidak ada yang terhapus dalam satu putaran: string seimbang akan menyusut hingga kosong, sedangkan string yang tidak seimbang akan tersangkut dengan karakter yang tersisa, seperti {(}) sejak awal.

Setiap putaran memindai seluruh string dan membuat salinan baru, dan string bersarang seperti (((...))) kehilangan satu pasang setiap putaran. Jumlahnya hingga n/2 putaran dengan pekerjaan O(n), atau total O(n²).

Algoritma

Hapus setiap (), [], dan {} dalam string.
Jika pada putaran itu tidak ada yang dihapus, berhenti.
Jika tidak, ulangi dengan string yang lebih pendek.
Kembalikan true jika string akhirnya kosong, dan false jika masih ada tanda kurung.

def isValid(s):
    while True:
        # Delete every adjacent matched pair in one round.
        shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
        if shorter == s:
            break  # nothing left to delete
        s = shorter
    return s == ""

Satu kali lintasan dengan stack

Intuisi

Tanda kurung penutup harus menutup tanda kurung yang paling baru dibuka dan masih terbuka. Tanda kurung yang dibuka terakhir ditutup pertama, dan urutan masuk terakhir, keluar pertama itulah yang disimpan oleh stack.

Masukkan tanda penutup yang ditunggu oleh setiap tanda pembuka. Tanda penutup harus sama dengan elemen teratas stack. Stack kosong berarti tidak ada tanda kurung yang perlu ditutup; elemen teratas yang berbeda berarti tanda kurung itu menutup jenis yang salah, seperti } dalam {(}) saat ) berada di posisi teratas. Pada akhirnya, apa pun yang tersisa di stack, seperti dalam ((, berarti tanda kurung itu dibuka tetapi tidak pernah ditutup. Setiap karakter dimasukkan atau dikeluarkan satu kali: waktu O(n), dan paling banyak ada n entri di stack.

Algoritma

Buat stack kosong.
Untuk tanda kurung buka, tambahkan pasangan penutupnya ke stack.
Untuk tanda kurung tutup, kembalikan false jika stack kosong atau elemen teratasnya adalah karakter yang berbeda; jika tidak, keluarkan elemen teratas.
Setelah karakter terakhir, kembalikan true hanya jika stack kosong.

def isValid(s):
    closers = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for ch in s:
        if ch in closers:
            stack.append(closers[ch])
        elif not stack or stack.pop() != ch:
            return False
    return not stack

Jebakan dan kasus tepi

Menghitung setiap jenis tanda kurung. {(}) memiliki jumlah yang sama dan tetap tidak valid, sedangkan )( gagal hanya karena urutannya.
Mengeluarkan elemen dari stack kosong. String yang diawali tanda kurung penutup, seperti } atau )]}, harus mengembalikan false, bukan menyebabkan crash.
Melewatkan pemeriksaan akhir. (([{ tidak pernah bertemu tanda kurung penutup yang salah, jadi hanya sisa elemen di stack yang menunjukkan bahwa string itu tidak valid.
Memercayai panjang string. Panjang ganjil selalu tidak valid, tetapi panjang genap tidak membuktikan apa pun: (] dan ())( sama-sama tidak valid.
Dalam pendekatan penghapusan, meneruskan tanda kurung ke ekspresi reguler atau pola Lua tanpa melakukan escape. ( dan [ memiliki makna khusus di sana. Gunakan penggantian teks biasa.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Valid Parentheses?

Solusi stack berjalan dalam waktu O(n), karena setiap karakter didorong atau dikeluarkan paling banyak satu kali. Dalam kasus terburuk, solusi ini menggunakan ruang O(n), yaitu untuk string yang hanya berisi tanda kurung pembuka. Menghapus pasangan yang cocok berulang kali membutuhkan waktu O(n²), karena string bertingkat dalam hanya kehilangan satu pasangan pada setiap putaran.

Mengapa stack digunakan untuk Valid Parentheses?

Kurung bersarang, jadi kurung yang dibuka terakhir harus ditutup terlebih dahulu. Stack menyimpan kurung tersebut di bagian teratas, sehingga kamu bisa membaca dan menghapusnya dalam waktu konstan. Dengan begitu, seluruh pemeriksaan tetap memiliki kompleksitas O(n).

Apakah string kosong merupakan tanda kurung yang valid?

Ya. String kosong tidak memiliki tanda kurung yang tidak berpasangan, jadi seimbang: stack tetap kosong, dan perulangan penghapusan tidak memiliki apa pun untuk dihapus. Dalam soal ini, s selalu memiliki setidaknya satu karakter.

def isValid(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "[]{}()"

Output yang diharapkan

true