Canonicalize an Absolute Unix-Style Path With Dot and Double-Dot Segments

Given an absolute path in a Unix-style file system, return its simplified canonical form.

Function Signature

def simplify_path(path: str) -> str:

Rules

Interpreting the input:

• path starts with /.
• A single period . refers to the current directory and is dropped.
• A double period .. moves up to the parent directory; at the root it stays at the root.
• Several consecutive slashes (for example //) act as a single slash.
• Any other sequence of characters between slashes is a directory or file name, including sequences of three or more periods such as ....

The canonical output:

• starts with a single /;
• separates names with exactly one /;
• has no trailing / unless the result is the root / itself;
• contains no . or .. components.

Constraints

• 1 <= len(path) <= 3000
• path consists of English letters, digits, ., /, and _.
• path is a valid absolute Unix path.

Examples

Example 1

Input: path = "/home//foo/"

Output: "/home/foo"

Explanation: the double slash collapses to one and the trailing slash is removed.

Example 2

Input: path = "/../"

Output: "/"

Explanation: moving up from the root stays at the root.

Example 3

Input: path = "/.../a/../b/c/../d/./"

Output: "/.../b/d"

Explanation: ... is an ordinary name; a/.. and c/.. cancel out, and . is dropped.

Canonicalize an Absolute Unix Path

Hints

1. Only a component that is exactly '.' or exactly '..' is special; '...', '.a', 'a..' and similar pieces are ordinary names.
2. A '..' cancels only the most recently kept name, and has no effect once you are back at the root.
3. Repeated slashes and a trailing slash never contribute a component of their own, so the answer depends only on the non-empty pieces between slashes.

Approach

Treat the path as a sequence of components separated by '/'. Scan them from left to right while keeping a stack of the names that make up the canonical path of the directory reached so far. An empty component (produced by the leading slash, by consecutive slashes, or by a trailing slash) and a '.' component leave the location unchanged, so they are skipped. A '..' component moves to the parent: pop the most recent name if the stack is non-empty; at the root the stack is empty and nothing happens. Every other component, including '...', '.a', 'a..' and any other name that merely contains periods, is an ordinary name and is pushed unchanged. Invariant: after a prefix of the components has been processed, the stack lists, from the root down, exactly the names of the directory that prefix resolves to. Each rule preserves the invariant, so at the end the canonical path is '/' followed by the stack joined with single slashes, and an empty stack yields the root '/'. This result starts with one '/', has exactly one '/' between names, has no trailing slash unless it is the root, and never contains '.' or '..' because those components are never pushed. Edge cases: the root '/' alone, paths made only of slashes or '.' components, more '..' than the current depth, '..' or '.' as the final component, and runs of slashes anywhere, including at the start.

• Time complexity: O(n)
• Space complexity: O(n)