Simplify Path
MEDIUMDescription
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:
- A single period
'.'represents the current directory. - A double period
'..'represents the previous/parent directory. - Multiple consecutive slashes such as
'//'and'///'are treated as a single slash'/'. - Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example,
'...'and'....'are valid directory or file names.
The simplified canonical path should follow these rules:
- The path must start with a single slash
'/'. - Directories within the path must be separated by exactly one slash
'/'. - The path must not end with a slash
'/', unless it is the root directory. - The path must not have any single or double periods (
'.'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 <= 3000pathconsists of English letters, digits, period'.', slash'/'or'_'.pathis a valid absolute Unix path.
Approaches
Checkout 2 different approaches to solve Simplify Path. Click on different approaches to view the approach and algorithm in detail.
Manual Parsing with a Stack
This approach improves upon the first one by avoiding the split() method. It manually iterates through the input path string to identify the components between slashes. This avoids the overhead of creating an intermediate array of components, making it more efficient in terms of both time and space, although the asymptotic complexity remains the same.
Algorithm
- Initialize a stack (e.g., a
Deque) and aStringBuilder. - Append a
/to the inputpathto ensure the last component is processed. - Iterate through the modified path character by character:
- If the character is not
/, append it to theStringBuilder. - If the character is
/, it marks the end of a component.- Process the string built in the
StringBuilder. - If it's
.., pop from the stack. - If it's not
.and not empty, push to the stack. - Reset the
StringBuilder.
- Process the string built in the
- If the character is not
- After the loop, build the final path from the stack as in the previous approach.
Instead of pre-processing the entire string with split(), we can parse it on the fly. We iterate through the path character by character, building up each component name. A component is defined as the sequence of characters between two slashes.
We use a StringBuilder to accumulate the characters of the current component. When we encounter a /, it signals the end of the current component. We then process this component just as in the previous approach: push for a directory name, pop for .., and ignore for . or empty.
To simplify the logic, it's helpful to append a / to the input path. This ensures that the last component is always followed by a slash, so we don't need special code to handle it after the loop finishes.
This method avoids creating a potentially large intermediate array of strings, leading to better memory usage and potentially faster execution time.
Here is the Java implementation:
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new LinkedList<>();
StringBuilder componentBuilder = new StringBuilder();
// Append a slash to handle the last component easily
String processingPath = path + "/";
for (char c : processingPath.toCharArray()) {
if (c == '/') {
if (componentBuilder.length() > 0) {
String component = componentBuilder.toString();
if (component.equals("..")) {
if (!stack.isEmpty()) {
stack.pollLast();
}
} else if (!component.equals(".")) {
stack.addLast(component);
}
// Reset builder for the next component
componentBuilder.setLength(0);
}
} else {
componentBuilder.append(c);
}
}
if (stack.isEmpty()) {
return "/";
}
return "/" + String.join("/", stack);
}
}
Complexity Analysis
Pros and Cons
- More efficient as it avoids creating an intermediate array of strings from
split(). - Lower memory overhead.
- Provides fine-grained control over the parsing logic.
- The implementation is slightly more complex than the
split()-based approach. - Requires careful manual handling of component boundaries.
Code Solutions
Checking out 4 solutions in different languages for Simplify Path. Click on different languages to view the code.
public class Solution {
public string SimplifyPath(string path) {
var stk = new Stack < string > ();
foreach(var s in path.Split('/')) {
if (s == "" || s == ".") {
continue;
}
if (s == "..") {
if (stk.Count > 0) {
stk.Pop();
}
} else {
stk.Push(s);
}
}
var sb = new StringBuilder();
while (stk.Count > 0) {
sb.Insert(0, "/" + stk.Pop());
}
return sb.Length == 0 ? "/" : sb.ToString();
}
}Video Solution
Watch the video walkthrough for Simplify Path
Similar Questions
5 related questions you might find useful
Data Structures:
Companies:
Subscribe to Scale Engineer newsletter
Learn about System Design, Software Engineering, and interview experiences every week.
No spam, unsubscribe at any time.