Simplify Path
Medium · Stack & Strings · String · Stack
Problem
You are given an absolute Unix-style file path path (it always starts with /). Return its canonical form.
In a Unix path, . means the current directory, .. means the parent directory (at the root, .. stays at the root), and several consecutive slashes act as a single /. Any other name, including one made only of periods such as ..., is an ordinary directory or file name.
The canonical path starts with a single /, separates names with exactly one /, does not end with / (unless it is just the root), and contains no . or .. components.
Examples
Input: path = "/docs//notes/./../img/" Output: "/docs/img"
The double slash collapses, . is dropped, and .. cancels notes.
Input: path = "/../x/.../y/.." Output: "/x/..."
The leading .. stays at the root, ... is an ordinary name, and the final .. removes y.
Input: path = "/./" Output: "/"
The path refers to the root itself.
Constraints
- 1 <= len(path) <= 3000
- path consists of English letters, digits, '.', '/' and '_'
- path is a valid absolute Unix path
Approaches
- Baseline: cancel the first ".." again and again — time O(n²), space O(n)
Follow-up
A shell resolves cd arguments the same way, except that a relative path starts from the current directory instead of the root. The first use case below adds that.
Related problems
Start free on Cariara · Coding problems · System design studio
