Simplify Path
Simplify Path: given an absolute Unix-style file path, return its simplified canonical form.
- 1 <= path.length <= 3000
- path consists of English letters, digits, period '.', slash '/' or '_'.
- path is a valid absolute Unix path.
Intuition
Simplify path converts a Unix-style absolute path into its canonical form, resolving . and .. and collapsing redundant slashes.
The structure of the problem is in .., which cancels the directory before it. That cancellation — most recent first — is exactly a stack:
- Split on slashes, push real directory names, and pop on ...
Splitting on / produces empty strings for consecutive slashes and for the leading slash. Those, along with ., are simply skipped, which handles // and /./ without any special logic.
The case that breaks implementations is .. at the root. /../ stays at / rather than failing, so popping an empty stack must be a no-op rather than an error. Guarding that pop is essential.
Directory names may contain dots — ... and ..hidden are valid names, not navigation. Only exactly . and exactly .. are special, so the comparison must be for equality, not for a leading dot.
Building the result joins the stack with / and prepends one, giving /a/b/c. An empty stack yields / alone, which is the correct canonical form for the root.
The result never has a trailing slash, so joining must not append one — a detail easy to get wrong when constructing the string manually rather than with a join.
Splitting is O(n) and each component is pushed and popped at most once, giving O(n) time and O(n) space.
Split on / and let a stack model the directory hierarchy: a name pushes, .. pops, and . or an empty segment is noise. The stack is the resulting path, so joining it produces the canonical form directly.
Approach
Before reading on: price up what the direct approach costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(n) time and O(n) space.
Recognise the cancellation
.. cancels the most recent directory, which is precisely a stack's behaviour. Everything else in the problem is parsing.
Split and skip the noise
Split on /. Empty strings from consecutive slashes and . are simply skipped, which handles // and /./ with no special logic.
Push real directory names
Anything that is not empty, ., or .. is a directory name and is pushed. The stack holds the resolved path so far.
Guard the pop at root
/../ stays at / rather than failing, so popping an empty stack must be a no-op. This is the case that breaks most implementations.
Compare for exact equality
... and ..hidden are valid directory names, not navigation. Test for exactly . and exactly .., never for a leading dot.
Join without a trailing slash
Prepend / and join the stack with /. An empty stack yields / alone, and the result never ends in a slash.
Cost of the approach
Splitting is O(n) and each component is pushed and popped at most once, giving O(n) time and O(n) space.
Solution & live demo
Common pitfalls
Popping an empty stack
if part == '..':
st.pop()if part == '..':
if st:
st.pop().. at the root has nowhere to go — /../ is just /. Popping unguarded throws on any path that tries to ascend past the root.
Not filtering empty segments
for part in path.split('/'):
st.append(part)if part == '' or part == '.':
continueConsecutive slashes and the leading slash produce empty strings from the split. Pushing them creates phantom directories and doubled separators in the output.
Joining without the leading slash
return '/'.join(st)
return '/' + '/'.join(st)
The canonical path is absolute and must begin at the root. Without the prefix an empty stack returns "" rather than "/", and every other path loses its leading separator.
Edge cases
The stack is empty so the pop is skipped and the result is "/".
Empty pieces are skipped, giving "/home/foo".
Two pops unwind a and b, leaving "/c".
Three dots is an ordinary directory name, not an up-level token — it is pushed.