- Use a stack to manage directory traversal since it allows us to go "up" a directory by popping from the stack
- Split the input path by '/' to process each component one by one
- Handle special cases like '.', '..', and empty strings resulting from consecutive '/'
- Rebuild the simplified path from the stack at the end
🤔What Did I Struggle With?
- Properly handling edge cases like:
- Extra slashes ('//')
- Paths with only root '/' or '.' and '..' without any valid directories
- Efficiently constructing the final simplified path from the stack
💡 Explanation of Solution
1. split the input path
- split the given string by the delimiter `/` to isolate directory names and commands (. , ..)
2. use a stack to manage directories
- skip elements that are empty (from consecutive slashes)
- or elements that represent the current directory (.)
3. reconstruct the simplified path
- combine the elements in the stack using '/' as the separator to create the simplified absolute path
- ensure the result starts with '/' as it represents the absolute path
4. edge cases
- paths like `/../` should simplify to `/` as we cannot go above the root directory
- paths with only `/` or `/./` should simplify `/`
⌛ Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n) due to auxilary space used for the stack
💻 Implementation of Solution
class Solution {public: string simplifyPath(string path) { stack<string> st; // Use a stack to manage directory traversal stringstream ss(path); string component; // Split the path by '/' while (getline(ss, component, '/')) { if (component == "." || component.empty()) { continue; // Ignore current directory or empty components } if (component == "..") { if (!st.empty()) { st.pop(); // Go up one level } } else { st.push(component); // Add valid directory name } } // Construct the simplified path from the stack string result; while (!st.empty()) { result = "/" + st.top() + result; // Prepend each directory st.pop(); } // Handle edge case for root directory return result.empty() ? "/" : result; }};