Simplify Path
The key idea
.. undoes the most recent step, which is exactly a pop; a single . or an empty piece (from //) is a no-op. Whatever names survive on the stack, joined by single slashes with a leading /, are the canonical path.Problem
You are given an absolute path for a Unix-style file system, which always begins with a slash /. Transform this absolute path into its simplified canonical path.
In a Unix-style file system, a period . refers to the current directory, a double period .. refers to the directory up a level, and any multiple consecutive slashes (that is, // or ///) are treated as a single slash /. For this problem, any other format of periods such as ... or .... are treated as valid directory or file names.
The simplified canonical path should follow these rules:
- It must start with a single slash /.
- Directories within the path are separated by exactly one slash /.
- It must not end with a slash /, unless it is the root directory.
- It must not include any single or double periods used to denote the current or parent directory.
Return the simplified canonical path.
Constraints
1 <= path.length <= 3000pathconsists of English letters, digits, period., slash/or_.pathis a valid absolute Unix path.
Examples
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization