Problem

Given an absolute path for a file (Unix-style), simplify it.

OR

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the 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 '/'.
  • The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Examples

Example 1:

1
2
3
4

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

Example 2:

1
2
3
4

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

Example 3:

1
2
3
4

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:

1
2
3
4

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

Example 5:

1
2
3
4

Input: path = "/.../a/../b/c/../d/./"
Output: "/.../b/d"
Explanation:
`"..."` is a valid name for a directory in this problem.

Solution

Method 1 - Using Stack and String Split Function

Looking at examples, we can see that the simplification process can be effectively managed using a stack due to the '..' operator:

  1. When encountering a file or directory name, push it onto the stack.
  2. When encountering '.', do nothing.
  3. When encountering '..', pop the top element from the stack (if any), as it signifies moving up to the parent directory.
  4. Ignore multiple consecutive slashes, treating them as a single '/'.

After traversing the entire string, the elements left in the stack form the simplified absolute path. To obtain the final result, we need to reverse these elements and concatenate them into a string.

So, the algorithm is:

  1. Split the given path using '/' as the delimiter.
  2. Use a stack to manage the folders and files.
  3. Traverse the split elements:
    • Push valid directory names onto the stack.
    • Ignore '.' and empty strings.
    • Pop the stack when encountering '..'.
  4. Construct the canonical path from the stack contents.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        Set<String> skip = Set.of(".", "", "..");

        for (String token : path.split("/")) {
            if ("..".equals(token)) {
                if (!stack.isEmpty()) stack.pop();
            } else if (!skip.contains(token)) {
                stack.push(token);
            }
        }

        StringBuilder ans = new StringBuilder();
        for (String dir : stack) {
            ans.insert(0, "/" + dir);
        }

        return ans.length() > 0 ? ans.toString() : "/";
    }
}
 
1
2
3

while (!stack.isEmpty()) {
	ans.append("/").append(stack.removeLast());
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack: List[str] = []
        skip = {".", "", ".."}

        for token in path.split("/"):
            if token == "..":
                if stack:
                    stack.pop()
            elif token not in skip:
                stack.append(token)

        ans: str = "/" + "/".join(stack)
        return ans

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the input path, due to the traversal and operations on the stack.
  • 🧺 Space complexity: O(n) for storing elements in the stack.