بررسی سوال Valid Parentheses در leetcode

سوال Valid Parentheses یکی از سوالات کلاسیک و پرتکرار در مصاحبههای برنامهنویسی و همچنین در پلتفرم لیتکد است. این سوال برای ارزیابی درک شما از ساختارهای دادهای مانند استک (Stack) بسیار مناسب است.

صورت مسئله

یک رشته شامل کاراکترهای (, ), {, }, [ و ] به شما داده میشود. شما باید بررسی کنید که آیا این رشته معتبر است یا خیر. یک رشته در شرایط زیر معتبر است:

1. پرانتزهای باز باید با همان نوع پرانتز بسته شوند.

2. پرانتزهای باز باید به ترتیب صحیح بسته شوند.

3. هر پرانتز بسته یک پرانتز باز از همان نوع دارد.

مثال‌ها

ورودی: "()"
خروجی: true

ورودی: "()[]{}"
خروجی: true

ورودی: "(]"
خروجی: false

ورودی: "([)]"
خروجی: false

ورودی: "{[]}"
خروجی: true

راه حل با استفاده از استک

بهترین راه حل برای این مسئله استفاده از ساختار داده استک است. ایده اصلی این است:

1. هر زمان یک پرانتز باز ((, {, [) مشاهده شد، آن را به استک اضافه کنیم.

2. هر زمان یک پرانتز بسته (), }, ]) مشاهده شد، بررسی کنیم آیا عنصر بالای استک متناظر با آن است یا نه.

3. اگر در هر مرحله شرط بالا برقرار نبود، رشته معتبر نیست.

4. در پایان، اگر استک خالی باشد، رشته معتبر است.

پیاده‌سازی در پایتون

python

def isValid(s: str) -> bool:
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    
    return not stack

پیاده‌سازی در جاوااسکریپت

javascript

function isValid(s) {
    const stack = [];
    const mapping = { ")": "(", "}": "{", "]": "[" };
    
    for (let char of s) {
        if (char in mapping) {
            const topElement = stack.length ? stack.pop() : '#';
            if (mapping[char] !== topElement) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    
    return stack.length === 0;
}

تحلیل پیچیدگی

• پیچیدگی زمانی: O(n) - زیرا هر کاراکتر را دقیقاً یک بار پردازش میکنیم.

• پیچیدگی فضایی: O(n) - در بدترین حالت ممکن است تمام کاراکترها را در استک ذخیره کنیم.

نکات مهم

1. حتماً موارد edge case مانند رشته خالی ("") را در نظر بگیرید که باید true برگرداند.

2. دقت کنید که ترتیب بسته شدن پرانتزها مهم است. مثلاً در ([)] ترتیب صحیح رعایت نشده است.

3. میتوانید از یک دیکشنری برای نگاشت پرانتزهای بسته به باز استفاده کنید تا کد تمیزتر شود.

این سوال پایه‌ای برای بسیاری از مسائل پیچیده‌تر است و تسلط بر آن به شما در حل مسائل مشابه کمک خواهد کرد.