71. Simplify Path Medium

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.

Approach

Input: A string path

Output: Return a more concise canonical path

This problem belongs to the Basic Stack category.

• We can split the path by /, and process each segment:
• Notice "" or ".": Skip (current directory).
• Notice "..": Pop from stack (return to previous level processing. If stack is empty, do nothing).
• Normal directory name: Push onto stack.
• Finally use '/' + '/'.join(stack) to connect into canonical absolute path.

Implementation

python

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for part in path.split('/'):
            if part == "" or part == ".":   # Empty part or current directory, ignore
                continue
            if part == "..":                # Previous level, pop from stack (if exists)
                if stack:
                    stack.pop()
            else:                           # Normal directory name, push
                stack.append(part)
        # Root directory is "/"; otherwise join with "/"
        return "/" + "/".join(stack)

javascript

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
    const stack = [];

    path.split('/').forEach(part => {
        if (part === '' || part === '.') return;

        if (part === '..') {
            if (stack.length) stack.pop();
        } else {
            stack.push(part);
        }
    });
    return '/' + stack.join('/');
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

71. Simplify Path (English)

71. 简化路径 (Chinese)