Longest Valid Parentheses
Kamu mendapatkan string s yang hanya terdiri dari karakter ( dan ). Temukan substring terpanjang (rangkaian karakter yang berurutan) yang tersusun dengan benar: setiap ( di dalamnya ditutup oleh ) yang muncul setelahnya di dalamnya, dan pasangan tanda kurung tersarang dengan benar, seperti pada (()()). Kembalikan panjang substring tersebut, atau 0 jika bahkan () pun tidak muncul.
Fungsi
- sstring
- serangkaian karakter ( dan )
- Mengembalikaninteger
- panjang substring valid terpanjang, atau 0 jika tidak ada
Batasan
1 ≤ s.length ≤ 6 × 104- Setiap karakter dari
sadalah(atau).
Contoh
- Input
- s = "()(())"
- Output
- 6
- Penjelasan
- Seluruh string tersusun dengan benar:
()diikuti(()). Dua bagian yang tersusun dengan benar jika disandingkan akan membentuk satu kesatuan, jadi jawabannya adalah semua 6 karakter.
- Input
- s = "())((())"
- Output
- 4
- Penjelasan
)pada indeks 2 tidak memiliki pasangan, jadi tidak ada jawaban yang melewatinya, dan(pada indeks 3 tidak pernah ditutup. Bagian terpanjang adalah(())pada indeks 4 hingga 7, dengan panjang 4, yang lebih panjang daripada()di awal.
- Input
- s = "))(("
- Output
- 0
- Penjelasan
- Kedua
)muncul sebelum kedua(, jadi tidak ada(yang pernah ditutup dan jawabannya adalah 0.
Pertanyaan lanjutan
Bisakah kamu juga melaporkan posisi awal substring yang terbentuk dengan benar dan paling panjang, dengan memilih yang paling kiri jika ada beberapa substring dengan panjang yang sama?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Baca substring dari kiri ke kanan dan jaga keseimbangan: +1 untuk
(, -1 untuk). Apa yang terjadi pada keseimbangan untuk substring yang tersusun dengan benar, dan apa yang ditunjukkan oleh)yang membuatnya turun di bawah nol tentang setiap substring yang melintasinya?Simpan tumpukan indeks karakter
(yang masih terbuka. Ketika)menutup karakter yang berada paling atas, rangkaian yang terbentuk dengan benar dan berakhir di sini dimulai tepat setelah indeks yang kini berada paling atas. Apa yang seharusnya ada di tumpukan saat tidak ada yang terbuka?Mulai stack dengan -1, yaitu indeks tepat sebelum string. Push indeks setiap
(. Saat menemukan), lakukan pop; jika stack kini kosong,)ini tidak akan pernah bisa dipasangkan, jadi push indeksnya sebagai basis baru; jika tidak, perulangan saat ini adalahidikurangi indeks yang berada di puncak. Pertahankan perulangan terpanjang yang kamu ukur.
Solusi
Bagian yang terbentuk dengan benar akan bergabung saat bersentuhan, jadi () dan (()) yang berdampingan membentuk satu rangkaian. Karakter tersendiri, seperti ) dalam ())(()), memutus string sehingga tidak ada rangkaian yang melewatinya. Stack berisi indeks dengan penanda dasar melacak tempat rangkaian saat ini dimulai dalam satu kali lintasan; dua lintasan penghitung melakukannya dengan memori O(1).
Tumbuhkan substring dari setiap titik awal
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Tetapkan titik awal, lalu berjalanlah ke kanan sambil menjaga keseimbangan: +1 untuk (, -1 untuk ). Rentang tersebut valid tepat ketika keseimbangannya kembali ke 0 tanpa pernah turun di bawahnya, jadi catat panjangnya setiap kali mencapai 0. Jika turun di bawah 0, berhentilah: ) itu tetap tidak berpasangan dalam setiap rentang yang lebih panjang dari titik awal ini.
Dalam 59998 ( yang diikuti (), setiap titik awal berjalan sampai akhir: sekitar n²/2 = 1.8 × 10^9 langkah untuk n = 6 × 10^4.
Algoritma
- Atur
bestke 0. - Untuk setiap start, atur
balanceke 0 dan telusuri end dari start hingga karakter terakhir. - Tambahkan 1 untuk
(dan kurangi 1 untuk). - Jika
balancekurang dari 0, hentikan start ini. Jika nilainya 0, perbaruibestdenganend - start + 1. - Kembalikan
best.
def longestValidParentheses(s):
best = 0
for start in range(len(s)):
balance = 0
for end in range(start, len(s)):
balance += 1 if s[end] == "(" else -1
if balance < 0:
# A ')' without a partner: no longer run starts here
break
if balance == 0:
best = max(best, end - start + 1)
return bestStack indeks dengan penanda dasar
Intuisi
Masukkan indeks ke stack, dan simpan satu indeks tambahan di bagian bawah: dasar, posisi tepat sebelum rangkaian saat ini, yaitu -1 di awal. Saat menemukan (, masukkan indeksnya. Saat menemukan ), keluarkan indeks. Jika stack kini kosong, berarti kamu mengeluarkan dasar: ) ini tidak dapat menutup apa pun, jadi indeksnya menjadi dasar yang baru. Jika tidak, elemen teratas adalah karakter terakhir sebelum rangkaian yang berakhir di i, yaitu ( pembuka atau dasar, sehingga panjang rangkaiannya adalah i - top.
Dasar menggabungkan bagian-bagian yang bersentuhan. Pada ()(()), ) terakhir mengeluarkan indeks 2 dan menemukan -1 di bagian teratas: 5 - (-1) = 6. Pada ())((()), indeks 2 mengeluarkan dasar dan menjadi dasar yang baru, lalu ) terakhir mengeluarkan 4 dan menemukan ( pembuka di indeks 3: 7 - 3 = 4.
Setiap indeks dimasukkan dan dikeluarkan paling banyak satu kali: waktu O(n).
Algoritma
- Mulai dengan stack yang berisi -1 dan tetapkan
bestke 0. - Untuk setiap indeks
i, masukkanijikas[i]adalah(. - Jika nilainya
), keluarkan satu elemen. - Jika stack sekarang kosong, masukkan
isebagai basis baru. Jika tidak, perbaruibestdengani - top. - Kembalikan
best.
def longestValidParentheses(s):
# The bottom of the stack is the index just before the current run
stack = [-1]
best = 0
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
stack.pop()
if not stack:
# This ')' has no partner: it becomes the new base
stack.append(i)
else:
best = max(best, i - stack[-1])
return bestHitung pembukaan dan penutupan dalam dua tahap
Intuisi
Telusuri dari kiri ke kanan sambil menghitung opens dan closes sejak reset terakhir. Jumlah yang sama berarti semua bagian sejak reset tersusun dengan benar, dengan panjang 2 × closes. Saat closes lebih banyak, sebuah ) tidak memiliki pasangan, jadi reset keduanya. Sebuah ( yang tidak pernah ditutup akan membuat opens terus lebih banyak, jadi pada (() langkah ini tidak menemukan apa pun. Telusuri lagi dari kanan ke kiri, lakukan reset saat opens lebih banyak, lalu ambil jawaban yang lebih besar.
Dua langkah sudah cukup. Rentang terpanjang dibatasi oleh karakter yang tidak dapat dipasangkan atau oleh ujung-ujungnya. Jika batas kirinya adalah ) yang tidak berpasangan atau awal rentang, langkah dari kiri akan melakukan reset di awal rentang. Jika batas kirinya adalah ( yang tidak berpasangan, batas kanannya tidak mungkin berupa ), karena itu akan menutup ( tersebut dan memperpanjang rentang, jadi langkah dari kanan akan menemukannya.
Algoritma
- Atur
best,opens, dancloseske 0. - Telusuri dari kiri ke kanan sambil menghitung setiap karakter. Saat jumlahnya sama, perbarui
bestdengan2 × closes. Saat jumlahcloseslebih besar, atur ulang keduanya ke 0. - Atur ulang kedua penghitung, lalu telusuri dari kanan ke kiri dengan cara yang sama, dan atur ulang saat jumlah
openslebih besar. - Kembalikan
best.
def longestValidParentheses(s):
best = 0
# Left to right: more ')' than '(' ends every run that started earlier
opens = closes = 0
for ch in s:
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * closes)
elif closes > opens:
opens = closes = 0
# Right to left: catches the runs that an unmatched '(' hid from the first pass
opens = closes = 0
for ch in reversed(s):
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * opens)
elif opens > closes:
opens = closes = 0
return best
Jebakan dan kasus tepi
- Menghitung pasangan yang cocok di seluruh string.
())((())memiliki 3 pasangan, tetapi pasangan-pasangan itu tidak semuanya berdekatan, jadi jawabannya 4, bukan 6. - Mengukur rangkaian dari
(yang cocok. Pada()(()),)terakhir cocok dengan indeks 2, sehingga hasilnya 4 dan()di depannya terlewat. - Memulai dengan stack kosong, bukan nilai dasar -1 (0 di Lua dan R, yang posisinya dimulai dari 1).
)pertama dari())pun tidak memiliki apa pun untuk diukur. - Menjalankan penghitung hanya dalam satu arah.
(()menghasilkan 0 dari kiri ke kanan, dan())menghasilkan 0 dari kanan ke kiri. Jawaban untuk keduanya adalah 2. - Mengatur ulang penghitung saat nilainya sama. Rangkaian masih dapat bertambah, seperti pada
()().
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu dari Longest Valid Parentheses?
Solusi stack dan solusi penghitung dua tahap sama-sama berjalan dalam waktu O(n). Dalam kasus terburuk, stack membutuhkan memori O(n), misalnya untuk string yang hanya berisi (, sedangkan penghitung membutuhkan O(1). Mencoba setiap posisi awal membutuhkan waktu O(n²).
Apakah ada solusi pemrograman dinamis untuk Longest Valid Parentheses?
Ya. Misalkan end[i] adalah rangkaian terpanjang yang terbentuk dengan benar dan berakhir di i, bernilai 0 jika s[i] adalah (. Jika s[i-1] adalah (, end[i] = end[i-2] + 2. Jika tidak, misalkan j = i - end[i-1] - 1; jika s[j] adalah (, end[i] = end[i-1] + 2 + end[j-1]. Nilai end[i] terbesar adalah jawabannya.
Apa perbedaan ini dengan Tanda Kurung Seimbang?
Valid Parentheses menanyakan apakah seluruh string tersusun dengan benar, dengan jawaban ya atau tidak yang dapat ditentukan oleh satu penghitung atau tumpukan. Di sini, kamu ingin mencari substring tersusun dengan benar yang paling panjang, jadi kamu juga melacak posisi awal setiap rentetan dan memulai ulang setelah karakter yang tidak mungkin memiliki pasangan.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def longestValidParentheses(s):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
s = "()(())"
Output yang diharapkan
6