Leetcode 71: Simplify Path

Input: A string representing the absolute path of a file or directory in a Unix-style file system.

Example: Input: path = "/home//docs/"

Constraints:

• 1 <= path.length <= 3000

• path consists of English letters, digits, period '.', slash '/', or '_'.

• The path is a valid absolute Unix path.

Output: Return the simplified canonical path as a string.

Example: Output: "/home/docs"

Constraints:

• The output must be a valid simplified absolute path.

Goal: Simplify the absolute Unix path by handling '.' and '..' according to file system rules.

Steps:

• Split the path by the '/' character.

• Iterate through each segment of the path.

• Push valid directory names onto a stack, and pop the stack when encountering '..'.

• Ignore '.' and empty segments.

• Finally, reconstruct the canonical path from the stack.

Goal: The input path must be a valid absolute path, and the function must handle all possible edge cases efficiently.

Steps:

• 1 <= path.length <= 3000

• The input path must be a valid Unix absolute path.

Assumptions:

• The input path is well-formed and always starts with a slash ('/').

• The path is an absolute Unix-style file system path.

• Input: Input: path = "/home//docs/"

• Explanation: Multiple consecutive slashes are treated as a single slash, resulting in the simplified path '/home/docs'.

• Input: Input: path = "/home/user/../data/files/"

• Explanation: The '..' refers to the parent directory, simplifying the path to '/home/data/files'.

Approach: Use a stack-based approach to simplify the Unix path by processing each component in sequence.

Observations:

• The problem requires handling several path components, including valid directory names, '.' (current directory), and '..' (parent directory).

• A stack data structure is useful for maintaining the current directory context.

• The challenge is to correctly handle '..' and '.' while ignoring extraneous slashes and invalid period-based directory names.

Steps:

• Split the input path into components using '/' as a delimiter.

• Process each component and update the stack based on the rules for '.' and '..'.

• Reconstruct the canonical path by joining the stack elements, making sure to handle the leading slash and removing any trailing slashes unless the result is the root directory.

Empty Inputs:

• An empty input is not possible due to the constraints (1 <= path.length).

Large Inputs:

• Handle the largest possible input, where the length of the path is 3000 characters.

Special Values:

• Handle cases like '/..' where going up from the root directory results in the root directory itself.

Constraints:

• The solution must efficiently handle large inputs while simplifying the path.

string simplifyPath(string path) {
    
    set<string> dot = {"..", ".", ""};
    
    string res = "", tmp;
    stringstream ss(path);
    
    stack<string> stk;
    
    while(getline(ss, tmp, '/')) {
        if(tmp == ".." && !stk.empty()) stk.pop();
        else if (!dot.count(tmp)) stk.push(tmp);
    }

    while(!stk.empty()) {
        res = "/" + stk.top() + res;
        stk.pop();
    }
    return res == ""? "/": res;
}

1 : Function Declaration

string simplifyPath(string path) {

Declares a function `simplifyPath` that takes a string `path` as input and returns a simplified path as a string.

2 : Set Initialization

    set<string> dot = {"..", ".", ""};

Creates a set `dot` to store invalid path segments: '..', '.', and empty strings.

3 : Variable Initialization

    string res = "", tmp;

Initializes `res` to store the simplified path and `tmp` to hold temporary path segments.

4 : String Stream Initialization

    stringstream ss(path);

Creates a string stream `ss` to parse the input `path`.

5 : Stack Initialization

    stack<string> stk;

Creates a stack `stk` to store valid path segments.

6 : Loop Iteration

    while(getline(ss, tmp, '/')) {

Iterates through each path segment in the string stream `ss`.

7 : Conditions

        if(tmp == ".." && !stk.empty()) stk.pop();

If the current segment is '..' and the stack is not empty, pop the top element from the stack (go back one directory).

8 : Conditions

        else if (!dot.count(tmp)) stk.push(tmp);

If the current segment is not a '.' or '..' or empty, push it onto the stack.

9 : Loop Iteration

    while(!stk.empty()) {

Iterates while the stack is not empty.

10 : String Concatenation

        res = "/" + stk.top() + res;

Concatenates the top element of the stack to the `res` string, prepending a '/'.

11 : Stack Operations

        stk.pop();

Pops the top element from the stack.

12 : Conditional Return

    return res == ""? "/": res;

Returns '/' if the `res` string is empty, otherwise returns the constructed simplified path.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: We process each character of the input path once, making the time complexity linear in terms of the path length.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is proportional to the number of components in the path, which can be at most n.

Leetcode 71: Simplify Path

Solution to LeetCode 71: Simplify Path Problem

Explore →