Skip to content

018 — Simplify Path

Source

  • Original source: Classic stack-simulation exercise
  • Platform: LeetCode — https://leetcode.com/problems/simplify-path/
  • Topic: stack (simulation)
  • Difficulty: Medium
  • Pattern: stack simulation
  • Basic idea inherited from: Problem 1-এর matching/undo discipline — .. মানে "এক ধাপ undo" (pop), নাম মানে "এক ধাপ এগোও" (push)

1. Problem in simple words

তোমাকে একটা Unix-style absolute path দেওয়া আছে (সবসময় / দিয়ে শুরু), যেমন /a/./b/../../c/। সেটাকে canonical (সরলতম) রূপে আনতে হবে। নিয়ম গুলো:

  • একাধিক slash (//) একটা slash-এর সমান।
  • একটা . মানে "এই directory-তেই থাকো" — কিছুই বদলায় না।
  • একটা .. মানে "এক ধাপ উপরের directory-তে যাও"।
  • ফলাফল সবসময় / দিয়ে শুরু, শেষে কোনো trailing / থাকবে না (root / ছাড়া), আর directory-র মাঝে ঠিক একটা /।
"/home/"            -> "/home"
"/../"              -> "/"          (root-এর উপরে যাওয়া যায় না)
"/home//foo/"       -> "/home/foo"  (// একটা / এর সমান)
"/a/./b/../../c/"   -> "/c"

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-এর সবচেয়ে সস্তা জায়গা।

6. Real-life analogy

ভাবো তুমি একটা বড় building-এ ঘরের ভেতরে ঘর, তার ভেতরে আরও ঘর — এভাবে ঢুকছ। হাতে একটা কাগজে লিখে রাখছ কোন কোন ঘর পেরিয়ে এখানে এলে (stack)। নতুন ঘরে ঢুকলে নাম লেখো (push)। কেউ বলল "এক ধাপ পিছিয়ে যাও" (..) — শেষ লেখা নামটা কেটে দাও (pop)। "এখানেই থাকো" (.) — কিছু কোরো না। শেষে কাগজে যা পড়ে রইল, সেটাই তোমার আসল রাস্তা।

7. Visual explanation

/a/./b/../../c/-কে / দিয়ে ভেঙে একটা একটা টুকরো process করি (stack top ডানে):

টুকরো   মানে                       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"

8. Example input and output

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"

9. Brute force thinking

সরল চিন্তা: বারবার string-এর ভেতর pattern খুঁজে বদলাই — //-কে / বানাই, /./-কে / বানাই, /dir/../-কে / বানাই — যতক্ষণ আর কিছু বদলানো যায় না, তারপর trailing slash ছাঁটি।

যতক্ষণ 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 গুলোর অর্থ আলাদা।

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

15. Python solution

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 নেই; খালি হলে "/"।

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!।

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 করলেই দুটোই এমনিতে মিটে যায়।

21. Which basic problem this inherits from

ভিত্তি: Problem 1-এর push/pop/undo discipline; chapter-এর ../patterns.md Pattern 1 (Matching / Nesting / Undo) — এখানে "undo" মানে ..-এ এক ধাপ পিছিয়ে যাওয়া। token-এ ভাঙার অংশটুকু string-processing (../../02-arrays-and-strings/) থেকে।

22. Similar harder problems

23. Pattern learned

Stack as navigation/undo: "path simplify", "এক ধাপ পিছাও", "undo/redo" দেখলে token-এ ভাঙো; এগোনো = push, পিছানো = pop (খালি কিনা আগে দেখো), থেমে থাকা = ignore। শেষে stack জুড়লেই উত্তর।

24. Final summary

ভবিষ্যতের আমাকে: path = directory-নামের stack। split করে চালাও — .. pop (খালি হলে চুপ), ./খালি skip, বাকি সব push, শেষে '/' + '/'.join(stack)। trailing/একাধিক slash split-এর খালি token-এই মিটে যায়। "simplify path / canonical / undo navigation" দেখলেই stack ভাববে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।