Problem link ও উৎস
- **Original source:** Classic stack-simulation exercise
- **Platform:** LeetCode —
- **Topic:** stack (simulation)
- **Difficulty:** Medium
- **Pattern:** stack simulation
- **Basic idea inherited from:** Problem 1-এর matching/undo discipline — `..` মানে "এক ধাপ undo" (pop), নাম মানে "এক ধাপ এগোও" (push)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা Unix-style absolute path দেওয়া আছে (সবসময় `/` দিয়ে শুরু), যেমন `/a/./b/../../c/`। সেটাকে **canonical** (সরলতম) রূপে আনতে হবে। নিয়ম গুলো:
- একাধিক slash (`//`) একটা slash-এর সমান।
- একটা `.` মানে "এই directory-তেই থাকো" — কিছুই বদলায় না।
- একটা `..` মানে "এক ধাপ উপরের directory-তে যাও"।
- ফলাফল সবসময় `/` দিয়ে শুরু, শেষে কোনো trailing `/` থাকবে না (root `/` ছাড়া), আর directory-র মাঝে ঠিক একটা `/`।
```text
"/home/" -> "/home"
"/../" -> "/" (root-এর উপরে যাওয়া যায় না)
"/home//foo/" -> "/home/foo" (// একটা / এর সমান)
"/a/./b/../../c/" -> "/c"
```
### Input ও output {#8-example-input-and-output}
```text
Input : "/home/" -> "/home"
Input : "/../" -> "/"
Input : "/home//foo/" -> "/home/foo"
Input : "/a/./b/../../c/" -> "/c"
Edge case 1 (root) : "/" -> "/"
Edge case 2 (তিন dot নাম) : "/..." -> "/..." ("..." special না, বৈধ নাম)
Edge case 3 (অতিরিক্ত ..) : "/a/../../b/../c//.//" -> "/c"
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা বড় building-এ ঘরের ভেতরে ঘর, তার ভেতরে আরও ঘর — এভাবে ঢুকছ। হাতে একটা কাগজে লিখে রাখছ কোন কোন ঘর পেরিয়ে এখানে এলে (stack)। নতুন ঘরে ঢুকলে নাম লেখো (push)। কেউ বলল "এক ধাপ পিছিয়ে যাও" (`..`) — শেষ লেখা নামটা কেটে দাও (pop)। "এখানেই থাকো" (`.`) — কিছু কোরো না। শেষে কাগজে যা পড়ে রইল, সেটাই তোমার আসল রাস্তা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **Problem 1 (valid parentheses)**-এর undo-discipline-এর ছদ্মবেশী রূপ। সেখানে closing bracket এসে সবচেয়ে recent খোলা context pop করত; এখানে `..` এসে সবচেয়ে recent ঢোকা directory pop করে — মানে "শেষ যেখানে ঢুকেছিলাম, সেখান থেকে বেরিয়ে আসি"। সাধারণ নাম এলে push। এক কথায়: navigation = push/pop discipline, যেখানে `..` হলো undo।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **invariant**: যেকোনো মুহূর্তে stack ধরে রাখে "এই মুহূর্তে আমি root থেকে যে directory গুলোর ভেতরে আছি, ঠিক সেই ক্রমে"। path-এর প্রতিটা টুকরো এই অবস্থাকে একভাবে বদলায়:
- খালি টুকরো বা `.` → অবস্থা একই (কোনো নড়াচড়া নেই)।
- `..` → এক ধাপ পিছিয়ে যাও, মানে top pop (তবে ইতিমধ্যে root-এ থাকলে কিছুই করার নেই — root-এর উপরে কিছু নেই)।
- আসল নাম → ভেতরে এক ধাপ ঢোকো, মানে push।
শেষে stack-এর element গুলো `/` দিয়ে জুড়লেই canonical path।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **stack** (Python-এ `list`) যেখানে আসল directory-নাম গুলো ক্রমে জমে। সাথে কিছু লাগে না — `split('/')` দিয়ে টুকরো করা, তারপর একটা একটা টুকরো process করা।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
path navigation-এ "সবচেয়ে শেষে যে directory-তে ঢুকেছি, `..` এলে আগে সেখান থেকেই বেরোব" — এটাই হুবহু LIFO। stack-এর `append` (ঢোকা) আর `pop` (বেরোনো) দুটোই O(1)। array-র মাঝখানে কিছু করতে হয় না — সবসময় শুধু শেষ প্রান্তটা বদলায়, যেটা stack-এর সবচেয়ে সস্তা জায়গা।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: বারবার string-এর ভেতর pattern খুঁজে বদলাই — `//`-কে `/` বানাই, `/./`-কে `/` বানাই, `/dir/../`-কে `/` বানাই — যতক্ষণ আর কিছু বদলানো যায় না, তারপর trailing slash ছাঁটি।
```text
যতক্ষণ string বদলায়:
"//" -> "/"
"/./" -> "/"
"/X/../" -> "/" (X একটা নাম, .. নয়)
শেষে trailing "/" সরাও (root বাদে)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিবার একটা pattern বদলালে string নতুন করে বানাতে আর আবার পুরোটা scan করতে হয়। গভীর `..`-শৃঙ্খল (`/a/b/c/d/../../../..`) থাকলে এটা বহুবার পুরো string scan করে → সবচেয়ে খারাপে **O(n^2)**, আর regex/replace-এর সীমানা-কেস (`/...`, `/..abc`) সামলানো ভঙ্গুর। একবার split করে stack চালালে O(n)-তে নিখুঁত হয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: path-টা আসলে directory-নামের একটা ধারা, যেখানে `..` শুধু "শেষ নামটা বাতিল করো" আর `.`/খালি "কিছু না"। তাই string-কে token-এ ভেঙে নিলে প্রতিটা token-এর একটাই সরল কাজ থাকে — push, pop, বা ignore। জটিল string-pattern নিয়ে আর ভাবতে হয় না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`path.split('/')` দিয়ে টুকরো বানাও। প্রতিটা টুকরোয়: খালি (`""`) বা `.` হলে skip; `..` হলে stack খালি না থাকলে pop; নাহলে (আসল নাম) push। শেষে `'/' + '/'.join(stack)` ফেরত দাও — stack খালি থাকলে এটা ঠিক `'/'` দেয় (root)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** path-কে অক্ষরের সমুদ্র ভেবো না; ভাবো এটা directory-নামের একটা **stack-এর ইতিহাস**। তখন `..` মানেই "undo", আর পুরো সমস্যাটা bracket-matching-এর মতোই সরল হয়ে যায় — শুধু token গুলোর অর্থ আলাদা।
### ছবিতে বোঝা {#7-visual-explanation}
`/a/./b/../../c/`-কে `/` দিয়ে ভেঙে একটা একটা টুকরো process করি (stack top ডানে):
```text
টুকরো মানে action stack
"" শুরুর / থেকে আসা খালি skip []
"a" directory নাম push [a]
"." এখানেই থাকো skip [a]
"b" directory নাম push [a, b]
".." এক ধাপ উপরে pop b [a]
".." এক ধাপ উপরে pop a []
"c" directory নাম push [c]
"" trailing / থেকে খালি skip [c]
শেষ "/" + join([c]) = "/c"
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `/a/../../b/../c//.//`:
1. split → `['', 'a', '..', '..', 'b', '..', 'c', '', '.', '', '']`
2. `''` skip; `'a'` push → `[a]`
3. `'..'` pop a → `[]`; `'..'` stack খালি, কিছু না → `[]`
4. `'b'` push → `[b]`; `'..'` pop b → `[]`
5. `'c'` push → `[c]`
6. বাকি `''`, `.`, `''`, `''` সব skip → `[c]`
7. `'/' + '/'.join(['c'])` = `'/c'` → return `/c`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def simplify_path(path):
stack = []
for part in path.split('/'):
if part == '' or part == '.':
continue # খালি (// থেকে) বা current-dir -> কিছু না
elif part == '..':
if stack:
stack.pop() # এক ধাপ উপরে; root-এ থাকলে কিছু না
else:
stack.append(part) # আসল directory নাম -> ভেতরে ঢোকো
return '/' + '/'.join(stack) # খালি stack হলে ঠিক "/" দেয়
# ---- tests ----
assert simplify_path("/home/") == "/home"
assert simplify_path("/../") == "/"
assert simplify_path("/home//foo/") == "/home/foo"
assert simplify_path("/a/./b/../../c/") == "/c"
assert simplify_path("/a/../../b/../c//.//") == "/c"
assert simplify_path("/...") == "/..." # তিন-dot বৈধ নাম, special না
assert simplify_path("/") == "/" # root
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `stack = []` — এখন পর্যন্ত যে directory গুলোর ভেতরে আছি, ক্রমে।
- `for part in path.split('/')` — `/` দিয়ে টুকরো; `//` থাকলে মাঝে খালি string `''` আসে।
- `if part == '' or part == '.':` — খালি টুকরো বা current-dir, কিছু করার নেই।
- `elif part == '..':` — এক ধাপ উপরে; কিন্তু `if stack:` দিয়ে আগে দেখি stack খালি কিনা — root-এর উপরে যাওয়া যায় না, খালি stack-এ pop করলে error হতো।
- `else: stack.append(part)` — `.`, `..` বা খালি ছাড়া যা কিছু, সেটা আসল নাম — push (তাই `...`, `..a`-ও সাধারণ নাম)।
- `return '/' + '/'.join(stack)` — leading `/` সবসময়; join করায় মাঝে ঠিক একটা `/`, trailing slash নেই; খালি হলে `"/"`।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`simplify_path("/a/./b/../../c/")` → section 7-এর trace মতো শেষে stack `[c]`, ফল `/c`। `simplify_path("/...")` → `...` কোনো special token নয় বলে push হয়, ফল `/...`। `simplify_path("/")` → split-এ শুধু খালি টুকরো, stack খালি থাকে, `'/' + '' = '/'`। সব assert pass করে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — `split` O(n), তারপর প্রতিটা টুকরো একবার করে দেখা; প্রতিটা push/pop O(1)। শেষ `join`-ও O(n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — সবচেয়ে খারাপ ক্ষেত্রে (কোনো `..` নেই, যেমন `/a/b/c/d`) সব directory নাম stack-এ জমে; split-এর list-ও O(n)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `..`-এ stack খালি কিনা না দেখে সরাসরি `pop` — `/../`-এ খালি stack-এ pop করলে error।
- `.` আর `..` ছাড়াও `...`-কে special ভাবা — শুধু ঠিক `.` আর `..` special; বাকি সব বৈধ নাম।
- trailing slash বা একাধিক slash আলাদা করে সামলানোর চেষ্টা — `split('/')`-এর খালি token skip করলেই দুটোই এমনিতে মিটে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Problem 1-এর push/pop/undo discipline; chapter-এর [../patterns.md](../patterns.md) Pattern 1 (Matching / Nesting / Undo) — এখানে "undo" মানে `..`-এ এক ধাপ পিছিয়ে যাওয়া। token-এ ভাঙার অংশটুকু string-processing ([../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)) থেকে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Decode String (nested context, stack) —