Problem link ও উৎস
- **Original source:** Classic stack exercise
- **Platform:** LeetCode —
- **Topic:** stack
- **Difficulty:** Easy
- **Pattern:** matching / nesting (stack)
- **Basic idea inherited from:** raw push/pop discipline — খোলা bracket push করো, বন্ধ bracket এলে top-এর সাথে match করাও
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা string দেওয়া আছে, যাতে শুধু `(`, `)`, `[`, `]`, `{`, `}` — এই ছয় রকম bracket থাকে। বলতে হবে string-টা **ঠিকভাবে nested** কিনা।
ঠিকভাবে nested মানে তিনটা শর্ত একসাথে মানতে হবে:
- প্রতিটা খোলা bracket-এর একটা সঠিক *ধরনের* বন্ধ bracket আছে।
- প্রতিটা বন্ধ bracket সঠিক *order*-এ বন্ধ হচ্ছে — সবচেয়ে পরে খোলা bracket-টা সবার আগে বন্ধ হবে।
- শেষে কোনো খোলা bracket অমীমাংসিত থেকে যায় না।
```text
valid : () ()[]{} {[]} ([{}])
invalid : (] ([)] ( ]
```
### Input ও output {#8-example-input-and-output}
```text
Input : "()" -> Output: True
Input : "()[]{}" -> Output: True
Input : "(]" -> Output: False (ভুল partner)
Input : "([)]" -> Output: False (interleave, nest না)
Edge case 1 (খালি string): Input: "" -> Output: True (কিছু ভাঙার নেই)
Edge case 2 (শুধু খোলা) : Input: "(" -> Output: False (leftover)
Edge case 3 (শুধু বন্ধ) : Input: "]" -> Output: False (underflow)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা ম্যাট্রিওশকা (Russian nesting doll) ভাবো। তুমি বাইরের পুতুল খুলে ভেতরে আরেকটা পাও, সেটা খুলে আবার আরেকটা — খুলতে খুলতে ভেতরে যাও। বন্ধ করার সময় উল্টো: সবচেয়ে ভেতরের, মানে সবচেয়ে শেষে খোলা পুতুলটা আগে বন্ধ করতে হয়। মাঝখানেরটা আগে বন্ধ করতে চাইলে হবে না — ভেতরেরটা তখনো খোলা। bracket-ও ঠিক তাই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা stack-এর সবচেয়ে raw রূপ — **push আর pop-এর discipline**, কোনো twist ছাড়াই। তুমি যেই মুহূর্তে বুঝবে "সবচেয়ে recently খোলা জিনিসটাই সবার আগে বন্ধ হতে হবে", তখনই LIFO (Last In, First Out) structure-টা নিজে থেকে চোখে পড়বে। chapter-এর [../concept.md](../concept.md)-এ যে "থালার স্তূপ" analogy আছে, এটা ঠিক সেটারই সরাসরি প্রয়োগ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **invariant**: যেকোনো মুহূর্তে stack-টা ধরে রাখে "যে bracket গুলো খোলা হয়েছে কিন্তু এখনো বন্ধ হয়নি", সবচেয়ে নতুনটা উপরে।
এই invariant ধরলে correctness তিনটা failure mode-এ ভাগ হয়ে যায়:
- বন্ধ bracket এল কিন্তু stack খালি — কিছু খোলাই হয়নি যা বন্ধ করব (underflow)।
- বন্ধ bracket এল কিন্তু top-এর খোলা bracket-টা ভুল ধরনের (mismatch)।
- পুরো string শেষ কিন্তু stack-এ এখনো খোলা bracket পড়ে আছে (leftover)।
এই তিনটার একটাও ঘটলে string invalid; নাহলে valid।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **stack** (Python-এ একটা সাধারণ `list`)। সাথে একটা ছোট **hash map** যা প্রতিটা বন্ধ bracket-কে তার সঠিক খোলা সঙ্গীর সাথে map করে — যাতে match করা O(1)-তে হয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
nesting মানেই "সবচেয়ে recent খোলাটা আগে বন্ধ হয়" — আর এটাই হুবহু LIFO। stack-এর `append` (push) আর `pop` দুটোই O(1)। বন্ধ bracket এলে আমাদের শুধু সবচেয়ে recent খোলাটা দেখতে হয়, যেটা ঠিক stack-এর top। array-তে মাঝখানে খুঁজতে গেলে O(n) লাগত; stack ঠিক যে প্রান্তটা দরকার সেটাই সস্তা রাখে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: বারবার string scan করে পাশাপাশি থাকা মিলে-যাওয়া জোড়া (`()`, `[]`, `{}`) মুছে ফেলি, যতক্ষণ আর কিছু মোছা না যায়।
```text
"([)]" -> কোনো পাশাপাশি জোড়া নেই -> থামো -> string খালি না -> invalid
"(())" -> ভেতরের "()" মোছো -> "()" -> মোছো -> "" -> valid
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিবার একটা জোড়া মুছলে string-টা নতুন করে বানাতে আর আবার scan করতে হয়। সবচেয়ে খারাপ ক্ষেত্রে (যেমন `((((...))))`) এটা O(n) বার scan, প্রতিবার O(n) কাজ → **O(n^2)**। string বারবার নতুন করে গড়াটাও অপচয়। আমরা চাই একবার scan-এ, O(n)-তে কাজ শেষ করতে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একটা বন্ধ bracket-কে শুধু সবচেয়ে recently খোলা bracket-এর সাথেই মেলাতে হয়** — তার আগের কোনো খোলা bracket-এর কথা ভাবার দরকারই নেই। "সবচেয়ে recent খোলা"-টা ঠিক stack-এর top। তাই string একবার বাঁ থেকে ডানে হাঁটলেই হয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
string-এ একবার হাঁটো। খোলা bracket পেলে stack-এ push করো। বন্ধ bracket পেলে stack-এর top দেখো: যদি top ওই বন্ধ bracket-এর সঠিক partner হয়, pop করো (এই জোড়াটা মিটে গেল); নাহলে (অথবা stack খালি থাকলে) সাথে সাথে invalid। শেষে stack খালি হলে valid, নাহলে leftover খোলা bracket আছে — invalid।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "পুরো string-টা মিলিয়ে দেখব" ভাবার বদলে ভাবো "প্রতি মুহূর্তে আমি *কীসের ভেতরে* আছি?" — stack-টাই তার exact উত্তর, innermost context উপরে। এই দৃষ্টিভঙ্গিতে nested-matching problem হঠাৎ trivial হয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`([{}])` valid কিনা দেখি, stack বদলাতে দেখি:
```text
char action stack (top ডানে)
'(' open -> push [ (
'[' open -> push [ (, [
'{' open -> push [ (, [, {
'}' close -> top '{' মেলে -> pop [ (, [
']' close -> top '[' মেলে -> pop [ (
')' close -> top '(' মেলে -> pop [
end stack খালি -> VALID
```
এবার `([)]` — interleave করে, nest করে না:
```text
'(' push [ (
'[' push [ (, [
')' close -> top '[', দরকার '(' -> MISMATCH -> invalid
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `"{[]}"`:
1. শুরু: `stack = []`
2. `{` — খোলা, push → `stack = ['{']`
3. `[` — খোলা, push → `stack = ['{', '[']`
4. `]` — বন্ধ, top `[` দরকার `[` ✓ pop → `stack = ['{']`
5. `}` — বন্ধ, top `{` দরকার `{` ✓ pop → `stack = []`
6. string শেষ, `stack` খালি → return `True`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def is_valid(s):
pairs = {')': '(', ']': '[', '}': '{'} # বন্ধ -> তার সঠিক খোলা
stack = []
for ch in s:
if ch in '([{':
stack.append(ch) # খোলা bracket জমাও
elif not stack or stack.pop() != pairs[ch]:
return False # underflow বা ভুল partner
return not stack # leftover থাকলে False
# ---- tests ----
assert is_valid("()") is True
assert is_valid("()[]{}") is True
assert is_valid("{[]}") is True
assert is_valid("([{}])") is True
assert is_valid("(]") is False # ভুল partner
assert is_valid("([)]") is False # interleave
assert is_valid("") is True # খালি string
assert is_valid("(") is False # leftover খোলা
assert is_valid("]") is False # underflow
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `pairs = {...}` — প্রতিটা বন্ধ bracket-কে তার সঠিক খোলা সঙ্গীর সাথে map; O(1) lookup-এর জন্য।
- `stack = []` — খোলা-কিন্তু-অমীমাংসিত bracket গুলো এখানে জমবে।
- `if ch in '([{':` — খোলা bracket হলে `append` করে stack-এ তুলে রাখো।
- `elif not stack or stack.pop() != pairs[ch]:` — বন্ধ bracket-এর ক্ষেত্রে: stack খালি হলে (underflow) বা pop করা top ভুল partner হলে — `False`। (`not stack` আগে check হয় বলে খালি stack-এ `pop` হয় না।)
- `return not stack` — পুরো string ঠিক থাকলেও যদি stack-এ leftover খোলা থাকে, `False`; খালি হলে `True`।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`is_valid("{[]}")` → section 14-এর dry run মতো stack শেষে খালি → `True`। `is_valid("([)]")` → `)` আসার সময় top থাকে `[`, partner দরকার `(`, mismatch → `False`। সব assert pass করে শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
array-কে stack হিসেবে; closing bracket এলে top-এর সাথে match।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// is the bracket string properly nested? (stack)
function isValid(s) {
const pairs = { ")": "(", "]": "[", "}": "{" }; // বন্ধ -> তার সঠিক খোলা
const stack = [];
for (const ch of s) {
if (ch === "(" || ch === "[" || ch === "{") {
stack.push(ch); // খোলা bracket জমাও
} else if (stack.length === 0 || stack.pop() !== pairs[ch]) {
return false; // underflow বা ভুল partner
}
}
return stack.length === 0; // leftover থাকলে false
}
// ---- test cases (example + edge) ----
assert(isValid("()") === true, "simple");
assert(isValid("()[]{}") === true, "all-types");
assert(isValid("{[]}") === true, "nested");
assert(isValid("([{}])") === true, "deep");
assert(isValid("(]") === false, "wrong-partner");
assert(isValid("([)]") === false, "interleave");
assert(isValid("") === true, "empty"); // edge
assert(isValid("(") === false, "leftover"); // edge
assert(isValid("]") === false, "underflow"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** plain array-ই stack — `push`/`pop` দুটোই O(1)। `stack.length === 0` আগে check করো (short-circuit `||`), নইলে খালি stack-এ `pop()` `undefined` দিয়ে ভুল match হতে পারত। শেষে `stack.length === 0` না দেখলে `"((("` ভুল করে valid দেখাবে।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function isValid(s: string): boolean {
const pairs: Record