Leetcode 020 Valid Parentheses

Soru

Given a string s containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Örnek 1

Input: s = "()[]{}"
Output: true

Örnek 2

Input: s = "([)]"
Output: false

Çözüm

• Verilen bir parantez dizisinin geçerli olup olmadığını kontrol etmenizi isteyen bir problem. Bu sorunda amaç, tüm açık parantezlerin uygun bir şekilde kapatılmış olup olmadığını belirlemektir. Geçerli bir parantez dizisi için, her açık parantez ('(', ‘{’, ‘[') karşılık gelen kapanış paranteziyle (')’, ‘}’, ‘]') eşleşmelidir.
• Bu tür problemler genellikle bir yığın (stack) veri yapısı kullanılarak çözülür. Yığın, son giren ilk çıkar (LIFO) prensibiyle çalışır ve açılan parantezlerin sırasını takip etmek için idealdir.
• Çalışma Mekanizması:
• Yığın İnitialize Edilmesi: Parantezlerin açılış sırasını takip etmek için bir yığın (stack) oluşturulur.
• Eşleşme Sözlüğü: Kapanış parantezlerini ve karşılık gelen açılış parantezlerini içeren bir sözlük (matching) kullanılır.
• Dizi Üzerinde Dolaşma: String içindeki her karakter için: Eğer karakter bir açılış parantezi ise, yığına eklenir. Eğer karakter bir kapanış parantezi ise, yığının en üstündeki eleman çıkarılır ve bu elemanın karşılık gelen açılış parantezi olup olmadığı kontrol edilir.
• Geçerlilik Kontrolü: İşlemler sonunda, eğer yığın boşsa tüm parantezler doğru bir şekilde eşleşmiştir ve true döndürülür. Eğer yığında eleman kalmışsa, bu, açılmış ancak kapatılmamış parantezler olduğu anlamına gelir ve false döndürülür.

Code

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        matching = {')': '(', '}': '{', ']': '['}
        
        for char in s:
            if char in matching.values():
                stack.append(char)  # Açma parantezlerini yığına ekle
            elif char in matching:
                if not stack or stack.pop() != matching[char]:
                    return False  # Eşleşmeyen veya yığında açılmamış bir kapanış parantezi varsa
        return not stack  # Yığın boşsa, tüm parantezler eşleşmiştir

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n), burada n girdi stringinin uzunluğudur. String boyunca tek bir geçiş yapılır.
• Space complexity (Alan Karmaşıklığı) : O(n), en kötü durumda tüm parantezler yığına eklenir (örneğin tümü açılış parantezi olduğunda).