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:

1. Split the input string using / as a delimiter.
2. 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.
3. Reconstruct the canonical path by joining stack elements with /.
4. 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.

Similar Problems for Practice

1. Simplify Windows Path
2. Evaluate Reverse Polish Notation
3. Valid Parentheses