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.

Example 1:

1Input: path = "/home/"
2Output: "/home"
3Explanation: The trailing slash should be removed.

Example 2:

1Input: path = "/home//foo/"
2Output: "/home/foo"
3Explanation: Multiple consecutive slashes are replaced by a single one.

Example 3:

1Input: path = "/home/user/Documents/../Pictures"
2Output: "/home/user/Pictures"
3Explanation: A double period ".." refers to the directory up a level.

Example 4:

1Input: path = "/../"
2Output: "/"
3Explanation: Going one level up from the root directory is not possible.

Example 5:

1Input: path = "/.../a/../b/c/../d/./"
2Output: "/.../b/d"
3Explanation: "..." 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.

Solution

This problem can be solved using Stacks. First, we have to split the path by /. This will give us all directory names. Next, we iterate through these directory names and if we come across any valid names (that is path is not . or it’s not empty like in /// case), then we push that directory name into stack.

If we come across directory like .. and if the stack is non-empty, then we pop out of the stack. Eventually, when we have walked through all parts of the path, we will have simplified path. The next part is to join directory names available in the stack with / and return that as the result.

 1class Solution {
 2     public String simplifyPath(String path) {
 3        String[] parts = path.split("/");
 4        Stack<String> stack = new Stack<>();
 5
 6        for(String part : parts) {
 7            if (part.equals("..")) {
 8                if (!stack.isEmpty()) {
 9                    stack.pop();
10                }
11            } else if (!part.equals(".") && !part.isEmpty()) {
12                stack.push(part);
13            }
14        }
15
16        StringBuilder sb = new StringBuilder();
17        for(String part : stack) {
18            sb.append("/");
19            sb.append(part);
20        }
21
22        return sb.length() > 0 ? sb.toString() : "/";
23    }
24}
  • Time Complexity: O(n)
  • Space Complexity: O(n) as it is O(2n) because of array and stack, but simplified to O(n)