Description:
Given an absolute path for a Unix-style file system, which begins with a slash '/', transform this path into its simplified canonical path.
In Unix-style file system context, a single period '.' signifies the current directory, a double period ".." denotes moving up one directory level, and multiple slashes such as "//" are interpreted as a single slash. In this problem, treat sequences of periods not covered by the previous rules (like "...") as valid names for files or directories.
The simplified canonical path should adhere to the following rules:
- It must start with a single slash
'/'. - Directories within the path should be separated by only one slash
'/'. - It should not end with a slash
'/', unless it’s the root directory. - It should exclude any single or double periods used to denote current or parent directories.
Return the new path.
Examples:
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.
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.Solution in Python:
To solve the problem of simplifying an absolute Unix-style file path, we need to handle various components such as single periods (.), double periods (..), multiple slashes, and ensure that the result starts with a single slash and does not end with a slash (unless it’s the root directory).
- Split the Path: Break the input path into components based on the slash (‘/’) delimiter.
- Stack for Directory Management: Use a stack to manage the directories. This helps in efficiently handling ‘..’ (move up a directory) and ‘.’ (current directory).
- Process Each Component:
- Ignore empty components and single periods (‘.’).
- Pop from the stack for double periods (‘..’), if the stack is not empty.
- Push valid directory names onto the stack.
- Construct the Simplified Path: Join the components in the stack with slashes and ensure the path starts with a slash.
Python
class Solution:
def simplifyPath(self, path: str) -> str:
# Split the path by '/' and filter out empty strings
components = path.split('/')
# Stack to hold the valid path components
stack = []
# Process each component
for component in components:
if component == '' or component == '.':
# Skip empty components and single periods
continue
elif component == '..':
# Move up one directory if possible
if stack:
stack.pop()
else:
# It's a valid directory name, add to stack
stack.append(component)
# Construct the canonical path
canonical_path = '/' + '/'.join(stack)
return canonical_pathDetailed Comments:
- Splitting the Path:
components = path.split('/')splits the path by slashes. This gives us a list of directory names, which can include empty strings due to consecutive slashes. - Using a Stack: The stack is initialized as an empty list. We use it to store the valid path components.
- Processing Each Component:
if component == '' or component == '.': continue: Skip over empty strings and single periods because they do not affect the path.elif component == '..':: If the component is ‘..’, pop from the stack if it’s not empty, effectively moving up one directory.else: stack.append(component): For any other valid directory name, simply add it to the stack.
- Constructing the Canonical Path: After processing all components, join the stack elements with slashes and prefix with a single slash to form the canonical path.
This solution ensures that we handle all edge cases and simplify the path correctly according to Unix-style file system rules.
Solution in Javascript:
JavaScript
/**
* @param {string} path
* @return {string}
*/
var simplifyPath = function(path) {
// Split the path by '/' and filter out empty strings
let components = path.split('/');
// Stack to hold the valid path components
let stack = [];
// Process each component
for (let component of components) {
if (component === '' || component === '.') {
// Skip empty components and single periods
continue;
} else if (component === '..') {
// Move up one directory if possible
if (stack.length > 0) {
stack.pop();
}
} else {
// It's a valid directory name, add to stack
stack.push(component);
}
}
// Construct the canonical path
// Join the stack elements with '/' and prefix with '/'
let canonicalPath = '/' + stack.join('/');
return canonicalPath;
};Solution in Java:
Java
import java.util.Stack;
class Solution {
public String simplifyPath(String path) {
// Split the path by '/' and filter out empty strings
String[] components = path.split("/");
// Stack to hold the valid path components
Stack<String> stack = new Stack<>();
// Process each component
for (String component : components) {
if (component.equals("") || component.equals(".")) {
// Skip empty components and single periods
continue;
} else if (component.equals("..")) {
// Move up one directory if possible
if (!stack.isEmpty()) {
stack.pop();
}
} else {
// It's a valid directory name, add to stack
stack.push(component);
}
}
// Construct the canonical path
StringBuilder canonicalPath = new StringBuilder();
// Join the stack elements with '/' and prefix with '/'
for (String dir : stack) {
canonicalPath.append("/").append(dir);
}
// If the stack is empty, return root "/"
return canonicalPath.length() > 0 ? canonicalPath.toString() : "/";
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
using System.Text;
public class Solution {
public string SimplifyPath(string path) {
// Split the path by '/' and filter out empty strings
string[] components = path.Split(new char[] {'/'}, StringSplitOptions.RemoveEmptyEntries);
// Stack to hold the valid path components
Stack<string> stack = new Stack<string>();
// Process each component
foreach (string component in components) {
if (component == ".") {
// Skip single periods
continue;
} else if (component == "..") {
// Move up one directory if possible
if (stack.Count > 0) {
stack.Pop();
}
} else {
// It's a valid directory name, add to stack
stack.Push(component);
}
}
// Construct the canonical path
StringBuilder canonicalPath = new StringBuilder();
// Join the stack elements with '/' and prefix with '/'
foreach (string dir in stack) {
canonicalPath.Insert(0, "/" + dir);
}
// If the stack is empty, return root "/"
return canonicalPath.Length > 0 ? canonicalPath.ToString() : "/";
}
}