{x}
blog image

Simplify Path

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 <= 3000
  • path consists of English letters, digits, period '.', slash '/' or '_'.
  • path is a valid absolute Unix path.

Solution Explanation: Simplifying Unix-style File Paths

This problem involves simplifying a given Unix-style absolute file path. The simplification process involves handling special characters (. and ..), removing redundant slashes, and ensuring the resulting path adheres to Unix conventions.

The most efficient approach uses a stack data structure. Let's break down the solution step-by-step:

1. Splitting the Path:

The input path string is first split into components using the / character as a delimiter. This creates an array or list of path segments.

2. Processing Path Segments:

Each path segment is then processed individually:

  • Empty or "." Segment: If the segment is empty or a single dot (.), it represents the current directory and is ignored.
  • ".." Segment: A double dot (..) indicates the parent directory. If the stack is not empty, the top element (representing the current directory) is popped from the stack. This simulates moving up one level in the directory hierarchy. If the stack is empty, it means we are already at the root, so no action is taken.
  • Other Segments: Any other segment represents a valid directory or file name. It's pushed onto the stack.

3. Constructing the Simplified Path:

After processing all segments, the stack contains the remaining valid directories. The simplified path is constructed by concatenating these directories, starting from the bottom of the stack (root) to the top. The resulting string is prefixed with a / to maintain the absolute path convention.

4. Handling Edge Cases:

  • Empty Stack: If the stack is empty after processing, it means the simplified path is just the root directory (/).
  • Trailing Slash: The algorithm inherently handles trailing slashes because redundant slashes are removed during the splitting and processing steps.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the input path string. This is because we iterate through the path segments once.
  • Space Complexity: O(n) in the worst case, as the stack might need to store all path segments if there are no ".." segments to remove.

Code Examples (Python):

The Python code efficiently implements this approach:

def simplifyPath(path: str) -> str:
    stack = []
    parts = path.split('/')
    for part in parts:
        if part == '' or part == '.':
            continue
        elif part == '..':
            if stack:
                stack.pop()
        else:
            stack.append(part)
    return '/' + '/'.join(stack)
 

Alternative Solution (using os.path.normpath in Python):

Python's os.path module provides a built-in function normpath which simplifies paths. It handles many aspects of path normalization, including resolving . and .. However, it might not handle all edge cases exactly as the problem statement specifies. It is a more concise option if the constraints are well understood.

import os
def simplifyPath(path: str) -> str:
    return os.path.normpath(path)
 

Remember that the stack-based approach provides a more robust and predictable solution for all possible inputs, conforming strictly to the problem's specifications. The os.path.normpath method is a convenient alternative if you trust its behavior in all scenarios.