#71

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Simplify Path

Simplify a Unix-style path by transforming it into its canonical form using stack-based state management.

Problem Statement

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 simplified path should follow rules such as removing redundant slashes, resolving '..' to move up a directory, and ignoring '.' which refers to the current directory.

For example, the path '/home/' should be simplified to '/home', and '/home//foo/' should be simplified to '/home/foo'. The '..' represents the parent directory, so '/home/user/Documents/../Pictures' should simplify to '/home/user/Pictures'.

Examples

Example 1

Input: path = "/home/"

Output: "/home"

The trailing slash should be removed.

Example 2

Input: path = "/home//foo/"

Output: "/home/foo"

Multiple consecutive slashes are replaced by a single one.

Example 3

Input: path = "/home/user/Documents/../Pictures"

Output: "/home/user/Pictures"

A double period ".." refers to the directory up a level (the parent directory).

Constraints

1 <= path.length <= 3000
path consists of English letters, digits, period '.', slash '/' or '_'.
path is a valid absolute Unix path.

Solution Approach

Process path components using a stack

For each part of the path, check if it's '..', '.', or a directory name. Use a stack to store valid directory names and pop from it when encountering '..'. Ignore '.' since it represents the current directory.

Join the stack into the canonical path

After processing the path components, join the stack into a single string starting with a '/' to form the canonical path. Ensure the stack contains only valid directory names and no extraneous slashes.

Edge case handling

Consider edge cases like consecutive slashes, empty path components, or paths with only '.' or '..'. Ensure the solution handles paths like '/' or '////' which should return '/' and resolve paths like '/home/../' correctly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on how the path is processed. Each component of the path is processed once, resulting in a time complexity of O(n), where n is the length of the path. The space complexity is also O(n) due to the stack storage for path components, as each directory name is pushed onto the stack.

What Interviewers Usually Probe

Look for the candidate's ability to apply stack-based state management to a real-world path traversal problem.
Assess how well the candidate handles edge cases like empty or root paths and redundant slashes.
Check for clear and efficient processing of the path string and stack manipulation.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle consecutive slashes as a single slash, which can lead to incorrect paths.
Failing to correctly manage the '..' operation to navigate to the parent directory.
Not accounting for the path starting with a slash, which is an important aspect of an absolute path.

Follow-up variants

Modify the problem to handle relative paths in addition to absolute paths.
Handle cases where the input path contains symbolic links or references to special directories like '/var'.
Extend the problem to handle a file system with deeper nested directories.

FAQ

What is the key pattern for solving the Simplify Path problem?

The key pattern is stack-based state management, where each component of the path is processed and pushed onto a stack, with special handling for '..' to move up one directory.

How do you handle consecutive slashes in Simplify Path?

Consecutive slashes should be treated as a single slash, so when processing the path, consecutive slashes are ignored or collapsed into one.

What should happen if the input path is just '/'?

If the path is just '/', the output should be '/', representing the root directory of the file system.

How should '..' be handled in the Simplify Path problem?

The '..' should move up one level in the directory tree. If the current directory is the root, '..' should be ignored.

Can Simplify Path be solved with a different approach than stack-based management?

While the stack-based approach is optimal for managing state, alternative approaches like recursion or manual string manipulation can be used but may be less efficient.

terminal

Solution

Solution 1: Stack

We first split the path into a number of substrings split by `'/'`. Then, we traverse each substring and perform the following operations based on the content of the substring:

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def simplifyPath(self, path: str) -> str:
        stk = []
        for s in path.split('/'):
            if not s or s == '.':
                continue
            if s == '..':
                if stk:
                    stk.pop()
            else:
                stk.append(s)
        return '/' + '/'.join(stk)

Continue Practicing

#32 longest valid parentheses #20 valid parentheses #224 basic calculator