Simplify Path

Given a Unix-style absolute file path, simplify it. Rules:

• "//" is treated as a single "/".
• "." means current directory (no effect).
• ".." means move up one directory if possible.
• The result must start with "/" and have no trailing "/" (unless it's the root).

Why this is worth learning

A lexical path stack models directory components. Dot and dot-dot have special meaning only as whole components; names such as ... are ordinary names.

Before coding: one-minute experiment

What does "/a/.../../b//./" simplify to?

Function signature

func SimplifyPath(path string) string

Inputs / outputs

• path: absolute Unix-style path.
• Return: simplified path.

Example

path = "/a/./b/../../c/"
Output: "/c"

Constraints

• 0 <= len(path) <= 100_000
• path contains letters, digits, '.', '/', and '_'.

Core idea (near-solution)

Split by '/', then process tokens with a stack:

• Ignore empty and "." tokens.
• Pop on ".." if possible.
• Otherwise push the directory name.

Invariant: the stack represents the canonical path components so far.

Algorithm (step-by-step)

1. Split the path by '/'.
2. For each token:
   • If token is empty or ".", skip.
   • If token is "..", pop if stack not empty.
   • Else push token.
3. Join stack with '/'. If empty, return "/".

Correctness sketch

After consuming a prefix of path components, the stack represents its canonical route from root. Empty components and a single dot leave the route unchanged. A double dot removes the most recent ordinary component when one exists; at root it has no effect because an absolute path cannot ascend above root. Any other component extends the route by that literal directory name. Each case preserves equivalence under the stated lexical rules. Joining the final components with one slash and adding the initial slash gives a canonical absolute path with neither redundant separators nor a trailing slash except at root.

Trace (hand walkthrough)

Example input:
path = "/a/./b/../../c/"
Output: "/c"

Walk:
- parts: a, ., b, .., .., c
- stack: [a] -> [a,b] -> pop b -> pop a -> [c]
- join -> "/c"

Pitfalls to avoid

• Treating ".." at root as error (it should stay at root).
• Returning a trailing slash.

Debugging lens

Do not treat every name containing a dot as special. Test attempts to go above root. This function does not access a filesystem, resolve symlinks, or establish security confinement.

Complexity

• Time: O(n)
• Extra space: O(n)

Implementation notes (Go)

• Use strings.Split(path, "/") and ignore empty or "." tokens.
• For "..", pop if possible; join remaining with "/".

Contract precision

This is lexical normalization only. The existing empty-input behavior returns "/". It is not a symlink-aware filesystem resolver.

Reconstruction checkpoint

What does "/a/.../../b//./" simplify to?

Return to Stack + Monotonic · Module quiz