LeetCode Solution 71 - Simplify Path

Problem Statement

Given a string path, which is an absolute path (starting with /) to a file or directory in a Unix-style file system, convert it to its simplified canonical path.

Constraints:

The path consists of English letters, digits, . (dot), / (slash), and _ (underscore).
Consecutive slashes should be considered as a single slash.
.. moves up one directory (if possible), while . means the current directory.
The simplified canonical path must always start with / and must not contain unnecessary slashes or dots.

Optimal Approach

The optimal approach is to use a stack to process directory names and handle . and .. efficiently.

Algorithm:

Split the input string using / as a delimiter.
Use a stack to process valid directory names:
- Ignore empty parts and ..
- Pop from the stack for .. (if possible) to move up one directory.
- Push valid directory names onto the stack.
Reconstruct the canonical path by joining stack elements with /.
Return / if the stack is empty (root directory case).

LeetCode-Compatible Code Implementation (C++)

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> stack;
        stringstream ss(path);
        string temp;
        
        while (getline(ss, temp, '/')) {
            if (temp == "" || temp == ".") continue;
            if (temp == "..") {
                if (!stack.empty()) stack.pop_back();
            } else {
                stack.push_back(temp);
            }
        }
        
        string result = "/";
        result += join(stack, "/");
        return result;
    }
    
private:
    string join(vector<string>& vec, string delimiter) {
        string res;
        for (string& str : vec) {
            if (!res.empty()) res += delimiter;
            res += str;
        }
        return res;
    }
};

Step-by-Step Explanation

Input: `"/home//foo/../bar/./baz/"`

Processing Steps:

Step	Component	Stack State
1	`/home`	`["home"]`
2	`//`	`["home"]`
3	`foo`	`["home", "foo"]`
4	`..`	`["home"]`
5	`bar`	`["home", "bar"]`
6	`.`	`["home", "bar"]`
7	`baz`	`["home", "bar", "baz"]`
8	`/`	`["home", "bar", "baz"]`

Final Output: `"/home/bar/baz"`

Alternative Approaches

1. Using Deque Instead of Vector

Instead of vector<string>, we can use deque<string> for efficient pop_front().

2. Iterative String Processing

Instead of using stringstream, we can manually iterate over the path string, handling characters accordingly.

Best Solution & Why?

Approach	Time Complexity	Space Complexity	Explanation
Stack-Based (Best)	O(N)	O(N)	Uses a stack to efficiently track directory structure.
Iterative Processing	O(N)	O(N)	More manual handling of string operations.
Deque Implementation	O(N)	O(N)	Alternative to `vector`, but similar logic.

Complexity Analysis

Time Complexity: O(N), since we process each character once.
Space Complexity: O(N), as we store directory names in a stack.

Conclusion

Best Approach: Stack-based processing.
Key Takeaways: Handle .. carefully, ignore . and empty parts, construct the final path efficiently.

Problem Breakdown

Simplify a Unix-style absolute path by resolving . (current directory), .. (parent), and repeated slashes. The stack-based approach: split on /, push normal segments, pop on .., and skip empty and . segments.

Edge Cases

Multiple consecutive slashes collapse to one. .. at the root stays at the root — you cannot go above /. A path of only slashes simplifies to /. A trailing slash is removed in the canonical form.

Complexity and Follow-Ups

Time O(n) for a single pass, space O(n) for the stack. A follow-up might ask you to implement the same logic for a custom separator or to stream the path without splitting, which tests whether you understand the underlying state machine.