Valid Parentheses
Yalnızca (, ), [, ], { ve } parantez karakterlerinden oluşan bir s dizgesi alırsın. Parantezler dengeliyse true döndür: her kapanış parantezi, hâlâ açık olan en son parantezi kapatmalı, ikisi aynı türde olmalı ve sonunda açık parantez kalmamalıdır. Aksi hâlde false döndür.
Fonksiyon
- sstring
- kontrol edilecek parantez dizisi
- Döndürürboolean
- parantezlerin dengeli olup olmadığı
Kısıtlar
1 ≤ s.length ≤ 104syalnızca(,),[,],{ve}karakterlerini içerir.
Örnekler
- Girdi
- s = "[]{}()"
- Çıktı
- true
- Açıklama
- Üç çift yan yana durur ve her biri açıldıktan hemen sonra kapanır.
- Girdi
- s = "{[()()]}"
- Çıktı
- true
- Açıklama
- İki yuvarlak parantez çifti, köşeli parantez çiftinin içinde kapanır; köşeli parantez çifti de küme parantezi çiftinin içinde kapanır. Her kapatıcı, hâlâ açık olan en son açıcıyla eşleşir.
- Girdi
- s = "{(})"
- Çıktı
- false
- Açıklama
}, ondan sonra açılan(hâlâ açıkken gelir ve bu yüzden yanlış türdeki parantezi kapatır.
Ek soru
Dize yalnızca normal parantezlerden oluşsaydı, bunu yığın yerine tek bir sayaçla O(1) ek alan kullanarak kontrol edebilir miydin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Dizgeyi soldan sağa doğru oku. Bir kapatma parantezi geldiğinde, hangi açma parantezini kapatmasına izin verilir?
Yalnızca en son açılan ve hâlâ açık olan açılış parantezini kapatabilir. En son açılan ilk kapatılır: bir yığının tuttuğu sıra tam olarak budur.
Her açılış parantezini bir yığına ekle. Kapanış paranteziyle karşılaştığında yığın boş olmamalı ve en üstündeki parantez aynı türden olmalı; onu çıkarıp devam et. Dize bittiğinde yalnızca yığın boşsa dengelidir.
Çözüm
Parantezleri saymak yeterli değildir: {(}) açılış ve kapanış parantezlerinden birer tane içerir ama yine de hatalıdır, çünkü sıralama önemlidir. Bir yığın, hâlâ açık olan parantezleri açıldıkları sırayla tutar; böylece yığın kullanarak yapılan tek bir geçiş tüm dizgenin geçerli olup olmadığını belirler.
Eşleşen çiftleri tekrar tekrar kaldır
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her dengeli dizenin, {[()]} içindeki () gibi, ayraçları arasında hiçbir şey olmayan en içteki bir çifti vardır. Yan yana duran eşleşmiş bir çifti silmek, dizenin dengeli olup olmadığını asla değiştirmez. Bu yüzden bir turda hiçbir şey silinmeyene kadar silme işlemini tekrarla: dengeli bir dize boşalır, dengesiz bir dize ise {(}) başlangıçtan beri olduğu gibi, geride karakterler kalarak takılır.
Her tur dizenin tamamını tarar ve yeni bir kopya oluşturur; (((...))) gibi iç içe bir dize ise her turda bir çift kaybeder. Bu, O(n) iş yüküyle en fazla n/2 tur demektir; toplamda O(n²) olur.
Algoritma
- Dizedeki tüm
(),[]ve{}ifadelerini sil. - Bu turda hiçbir şey silinmediyse dur.
- Aksi takdirde daha kısa olan dizeyle tekrarla.
- Dize boş kaldıysa
true, herhangi bir parantez kaldıysafalsedöndür.
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 == ""Yığınla tek geçiş
Sezgi
Kapanış parantezi, hâlâ açık olan ve en son açılmış parantezi kapatmalıdır. Son açılan parantez ilk kapanır; bu son giren ilk çıkar sırası, yığının tuttuğu şeydir.
Her açılış parantezi için beklediği kapanış parantezini yığına ekle. Ardından bir kapanış parantezi, yığının tepesindekiyle eşleşmelidir. Boş bir yığın, kapatılacak hiçbir şey olmadığı anlamına gelir; tepedeki farklı bir parantez türü ise yanlış türü kapattığı anlamına gelir; ) tepede dururken {(}) içindeki } gibi. Sonunda, (( örneğindeki gibi yığında kalan her şey açılmış ama hiç kapatılmamıştır. Her karakter yığına bir kez eklenir ya da yığından bir kez çıkarılır: O(n) zaman ve yığında en fazla n öğe.
Algoritma
- Boş bir yığın oluştur.
- Açılış parantezi için eşleşen kapanış parantezini yığına ekle.
- Kapanış parantezi için, yığın boşsa veya tepesindeki karakter farklıysa
falsedöndür; aksi takdirde elemanı çıkar. - Son karakterden sonra yalnızca yığın boşsa
truedöndür.
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
Tuzaklar ve uç durumlar
- Her tür parantezi ayrı ayrı saymak.
{(})eşleşen sayılara sahiptir ama yine de geçersizdir;)(ise yalnızca sıralama nedeniyle geçersizdir. - Boş bir yığından eleman çıkarmak.
}veya)]}gibi kapatan bir parantezle başlayan bir dizge, çökmek yerinefalsedöndürmelidir. - Son kontrolü atlamak.
(([{hiçbir zaman yanlış bir kapatan parantezle karşılaşmaz; bu nedenle geçersiz olduğunu yalnızca yığında kalanlar gösterir. - Uzunluğa güvenmek. Tek uzunluk her zaman geçersizdir, ancak çift uzunluk hiçbir şeyi kanıtlamaz:
(]ve())(ikisi de geçersizdir. - Silme yaklaşımında parantezleri kaçış karakteri kullanmadan bir düzenli ifadeye veya Lua kalıbına geçirmek.
(ve[burada özel bir anlama sahiptir; düz metin değiştirme kullanın.
Sıkça sorulan sorular3
Valid Parentheses algoritmasının zaman karmaşıklığı nedir?
Yığın çözümü O(n) zamanda çalışır, çünkü her karakter en fazla bir kez yığına eklenir veya yığından çıkarılır. En kötü durumda, yalnızca açıcı karakterlerden oluşan bir dizgede O(n) alan kullanır. Eşleşen çiftleri tekrar tekrar kaldırmak O(n²) zaman alır, çünkü derin iç içe geçmiş bir dizeden her turda yalnızca bir çift çıkarılır.
Geçerli Parantezler için neden yığın kullanılır?
Köşeli ayraçlar iç içe geçer; bu nedenle en son açılan köşeli ayraç ilk önce kapatılmalıdır. Bir yığın, bu köşeli ayracı en üstte tutar; böylece sabit zamanda okuyup kaldırabilirsin ve tüm denetim O(n) süresinde tamamlanır.
Boş bir dize geçerli bir parantez dizisi midir?
Evet. Boş bir dizgede eşleşmeyen parantez yoktur, bu yüzden dengelidir: yığın boş kalır ve kaldırma döngüsünün kaldıracağı hiçbir şey yoktur. Bu problemde s her zaman en az bir karakter içerir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def isValid(s):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
s = "[]{}()"Beklenen Çıktı
true