LeetCode 20 · Valid Parentheses · Easy

Yığınla Parantez Kontrolü

Çözümün her adımını burada izleyebilirsin. Bir metin seç, İleri'ye bas; hangi karakterin okunduğunu, yığının nasıl dolup boşaldığını ve kodun hangi satırının çalıştığını gör.

Fikir üç adımda

  1. 1

    Tabak yığını

    Açılan her parantezi bir tabak gibi üst üste koy. Yığında sadece en üstteki tabağa erişebilirsin: en son konan, ilk alınan olur. C#'ta bunun hazır sınıfı Stack<char>.

  2. 2

    Kapanan, en son açılanı kapatır

    {[()]} metninde ) geldiğinde kapatması gereken (, yani en son açılan. O da yığının en üstünde duruyor. Üstteki aynı türden değilse metin geçersiz.

  3. 3

    Sonunda yığın boş olmalı

    Metin bittiğinde yığında parantez kaldıysa bunlar açılıp hiç kapanmamış demektir. (( bu yüzden geçersiz. Boş yığındayken gelen kapanan parantez de geçersiz: )

Adım adım izle

Metin (altındaki küçük sayı karakterin sırası)

henüz okunmadı şu an okunan yığında bekliyor eşleşti hatalı

Yığın (en üstteki en yukarıda)

Pop() ile çıkan —

Değişkenler

Kod (Solution.cs içindeki metot)

Neden O(n)?

Her karakteri bir kez okuyoruz ve her parantez yığına en fazla bir kez girip bir kez çıkıyor. Metin 10.000 karakter de olsa yaklaşık 10.000 adımda biter: O(n) zaman. En kötü durumda, örneğin metin sadece açılan parantezlerden oluşuyorsa, hepsi yığına girer: O(n) bellek.