At first, this problem looks like a normal string manipulation question.
But the real idea is:
Simulating Unix directory navigation
We are given an absolute Unix path and need to convert it into its canonical form.
Example:
Input:
/home/user/Documents/../Pictures
Output:
/home/user/Pictures
Key Observations
-
.→ Current directory → Ignore -
..→ Go back to parent directory -
//→ Multiple slashes act as single slash - Normal folder names should be stored
Why Stack?
Whenever we see:
..
we must remove the previous directory.
That is exactly:
LIFO behavior
So stack becomes the perfect choice.
Approach
We process the path token by token.
Rules
- Ignore empty strings and
. - For
..→ pop from stack - Otherwise push folder name into stack
Finally, join everything using /.
C++ Code
class Solution {
public:
string simplifyPath(string path) {
vector<string> st;
string curr = "";
for (int i = 0; i <= path.size(); i++) {
if (i == path.size() || path[i] == '/') {
if (curr == "" || curr == ".") {
// Ignore
}
else if (curr == "..") {
if (!st.empty()) {
st.pop_back();
}
}
else {
st.push_back(curr);
}
curr = "";
}
else {
curr += path[i];
}
}
string ans = "";
for (string dir : st) {
ans += "/" + dir;
}
return ans.empty() ? "/" : ans;
}
};
Complexity
Time Complexity
O(n)
Space Complexity
O(n)
Final Note
This problem is a great example of how understanding system behavior makes implementation much easier.
Once you recognize:
".." = undo operation
the stack solution becomes very natural.
Top comments (0)