Stack: Valid Parentheses

Stack মনে রাখে কোন bracket এখনো খোলা আছে, আর সবশেষে খোলা bracket-টাকেই আগে বন্ধ করতে হয়।

মূল ধারণা

Stack অনেকটা একটার উপর আরেকটা রাখা প্লেট-এর মতো: নতুন প্লেট শুধু উপরে রাখা যায়, আর নেওয়াও যায় শুধু উপর থেকে (last in, first out)। Bracket check করতে text-এর উপর দিয়ে এক এক করে যান। প্রতিটা opening bracket stack-এ push করুন। প্রতিটা closing bracket-কে উপরের প্লেটের সাথে মিলতে হবে, মিললে সেই প্লেট সরিয়ে ফেলুন। না মিললে (বা stack খালি থাকলে) text invalid। শেষে stack অবশ্যই খালি থাকতে হবে।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity

Time complexity: O(n) – প্রতিটা অক্ষর একবার push বা pop হয়। Space complexity: O(n) সবচেয়ে খারাপ ক্ষেত্রে (সবগুলোই opening bracket হলে)।