یادداشت کامل الگوریتم

پرانتزهای معتبر

Valid Parentheses

Valid Parentheses بررسی می‌کند هر bracket باز با نوع درست و در ترتیب nesting صحیح بسته شود. Stack دقیقاً این رفتار تو در تو را مدل می‌کند.

نوعالگوریتمدستهمسائل کلاسیکسطحپایهپیچیدگی معمولVaries by implementation / input constraints

جواب کوتاه و حرفه‌ای

اول این مفهوم را در ذهن نگه دار

توضیح ساده

چطور کار می‌کند؟ ساده و مرحله‌ای

bracketهای باز را push کن.

برای هر bracket بسته، top را pop و type را مقایسه کن. در پایان Stack باید خالی باشد.

روند اجرا

الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان

constraint و edge case را بازگو کن.

pattern و invariant را پیدا کن.

قبل از کد یک مثال کوچک را دستی اجرا کن.

یک مثال کوچک برای فهم بهتر

یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای پرانتزهای معتبر هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.

پیاده‌سازی خوانا با JavaScriptJavaScript

function isValid(input) {
  const match = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const ch of input) {
    if ("([{ ".includes(ch) && ch !== " ") stack.push(ch);
    else if (match[ch] && stack.pop() !== match[ch]) return false;
  }
  return stack.length === 0;
}

این کد را چطور بخوانی؟

syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.

پیچیدگی

Varies by implementation / input constraints

این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.

چه زمانی استفاده کنیم؟

موارد مناسب

وقتی invariant pattern با constraint مسئله هماهنگ است از آن استفاده کن.

اشتباهات رایج

کجا معمولاً اشتباه می‌کنیم؟

قبل از تعریف invariant مستقیم سراغ کد نرو.
قبل از جواب صحیح ساده، زود optimization نکن.

در مصاحبه چطور توضیح بدهیم؟

مدل یک پاسخ حرفه‌ای

این سؤال نمونه خوبی برای انتخاب Data Structure از روی ماهیت مسئله است: آخرین bracket بازشده باید اول بسته شود، یعنی دقیقاً LIFO و Stack.

مسئله→ایده اصلی→Invariant / State→Big-O→Trade-off

چند سؤال مصاحبه‌ای سریع

پرانتزهای معتبر چه مسئله‌ای را حل می‌کند؟

درباره Complexity چه چیزی باید بگویم؟

پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.

رایج‌ترین اشتباه چیست؟

قبل از تعریف invariant مستقیم سراغ کد نرو.

موضوعات مرتبط برای ادامه مطالعهPatternهای حل مسئلهEdge CaseTrade-off پیچیدگی

function isValid(input) { const match = { ")": "(", "]": "[", "}": "{" }; const stack = []; for (const ch of input) { if ("([{ ".includes(ch) && ch !== " ") stack.push(ch); else if (match[ch] && stack.pop() !== match[ch]) return false; } return stack.length === 0; }