NeetCode #358LC-71MediumStackNC 250
← Back to All Problems#358 · #71 · Simplify Path(简化路径)
📌 Problem Statement & Constraints
Given an absolute Unix-style path, simplify it to its canonical form: it must start with a single
/, contain no . or .. components, no double slashes, and no trailing slash (except for the root). Constraints: 1 <= path.length <= 3000.💡 Core Algorithmic Approaches
- Split on
/and process the components with a stack. - Empty components (from
//) and.components are skipped. ..pops the stack if it is non-empty; on an empty stack it is a no-op (you cannot go above the root).- Join the surviving components with
/and prepend a leading slash.
💻 Benchmark Python3 Implementation
class Solution:
def simplifyPath(self, path: str) -> str:
st = []
for part in path.split("/"):
if part == "" or part == ".":
continue # skip empties and the current directory
if part == "..":
if st:
st.pop() # go up one level, but not above the root
else:
st.append(part)
return "/" + "/".join(st)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass over the components.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Popping on
..without the emptiness guard:st.pop()on an empty list raisesIndexError; going above the root must be a no-op. - Treating
.as a directory: it must be skipped. - Forgetting to skip empty components:
split('/')on"//"yields empty strings, which would create empty path segments. - Returning
"/".join(st)without the leading slash: the result must be absolute.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.