DSA problem
Simplify Path
Given an absolute path for a Unix-style file system, which begins with a slash '/', transform this 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 (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.
The canonical path should have the following format: the path starts with a single slash '/', any two directories are separated by a single slash, the path does not end with a trailing slash, and the path only contains the directories on the path from the root directory to the target file or directory (no '.' or '..').
The natural data structure here is a stack of directory names. Split the path by slashes — multiple consecutive slashes naturally produce empty tokens which we ignore. For each non-empty token: if it is '.', ignore it (it is the current directory); if it is '..', pop the stack (if non-empty — popping at the root is a no-op); otherwise push the token (a real directory name). At the end, join the stack contents with single slashes and prepend a leading slash. This is O(n) time and O(n) space.
Examples
path = "/home/""/home"path = "/../""/"path = "/home//foo/""/home/foo"Constraints
- 1 <= path.length <= 3000
- path consists of English letters, digits, period '.', slash '/' or '_'.
- path is a valid absolute Unix path.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.