You are given an absolute path for a Unix-style file system, which always begins with a slash '/'
. Your task is to transform this absolute path into its simplified canonical path.
The rules of a Unix-style file system are as follows:
'.'
represents the current directory.'..'
represents the previous/parent directory.'//'
and '///'
are treated as a single slash '/'
.'...'
and '....'
are valid directory or file names.The simplified canonical path should follow these rules:
'/'
.'/'
.'/'
, unless it is the root directory.'.'
and '..'
) used to denote current or parent directories.Return the simplified canonical path.
Example 1:
Input: path = "/home/"
Output: "/home"
Explanation:
The trailing slash should be removed.
Example 2:
Input: path = "/home//foo/"
Output: "/home/foo"
Explanation:
Multiple consecutive slashes are replaced by a single one.
Example 3:
Input: path = "/home/user/Documents/../Pictures"
Output: "/home/user/Pictures"
Explanation:
A double period ".."
refers to the directory up a level (the parent directory).
Example 4:
Input: path = "/../"
Output: "/"
Explanation:
Going one level up from the root directory is not possible.
Example 5:
Input: path = "/.../a/../b/c/../d/./"
Output: "/.../b/d"
Explanation:
"..."
is a valid name for a directory in this problem.
Constraints:
1 <= path.length <= 3000
path
consists of English letters, digits, period '.'
, slash '/'
or '_'
.path
is a valid absolute Unix path.This problem involves simplifying a given Unix-style absolute file path. The simplification process involves handling special characters (.
and ..
), removing redundant slashes, and ensuring the resulting path adheres to Unix conventions.
The most efficient approach uses a stack data structure. Let's break down the solution step-by-step:
1. Splitting the Path:
The input path string is first split into components using the /
character as a delimiter. This creates an array or list of path segments.
2. Processing Path Segments:
Each path segment is then processed individually:
.
), it represents the current directory and is ignored...
) indicates the parent directory. If the stack is not empty, the top element (representing the current directory) is popped from the stack. This simulates moving up one level in the directory hierarchy. If the stack is empty, it means we are already at the root, so no action is taken.3. Constructing the Simplified Path:
After processing all segments, the stack contains the remaining valid directories. The simplified path is constructed by concatenating these directories, starting from the bottom of the stack (root) to the top. The resulting string is prefixed with a /
to maintain the absolute path convention.
4. Handling Edge Cases:
/
).Time and Space Complexity:
Code Examples (Python):
The Python code efficiently implements this approach:
def simplifyPath(path: str) -> str:
stack = []
parts = path.split('/')
for part in parts:
if part == '' or part == '.':
continue
elif part == '..':
if stack:
stack.pop()
else:
stack.append(part)
return '/' + '/'.join(stack)
Alternative Solution (using os.path.normpath
in Python):
Python's os.path
module provides a built-in function normpath
which simplifies paths. It handles many aspects of path normalization, including resolving .
and ..
However, it might not handle all edge cases exactly as the problem statement specifies. It is a more concise option if the constraints are well understood.
import os
def simplifyPath(path: str) -> str:
return os.path.normpath(path)
Remember that the stack-based approach provides a more robust and predictable solution for all possible inputs, conforming strictly to the problem's specifications. The os.path.normpath
method is a convenient alternative if you trust its behavior in all scenarios.