Solution
The approach is to use a stack to store all the valid directory names and pop from the stack whenever we encounter “../” (or a “..” at the end of the string). We have to ignore all occurrences of “./” (or a “.” at the end of string) and “/”. Instead of using std::stack, let’s use std::vector as it retains the correct order of directories (instead of reversing it in a LIFO based stack) which will be helpful when we form our answer string. For better understanding, view the code:
string simplifyPath(string path) {
// sanity check
if (path == "")
return "";
string ans = "", s="";
vector<string> st;
for (int i=1; i<path.length(); ) {
// ignore if it is a slash
if (path[i] == '/') {
i++;
continue;
}
// check if it is "../" or ".." (only at the end of string)
if (path.substr(i, 3) == "../" || path.substr(i, 3) == "..") {
if (!st.empty())
st.pop_back();
i+=3;
continue;
}
// check if it is "./" or "." (only at the end of string)
if (path.substr(i,2) == "./" || path.substr(i,2) == ".") {
i+=2;
continue;
}
// push the directory name to stack
s="";
while (i<path.length() && path[i]!='/') s+=path[i++];
st.push_back(s);
}
for (string str : st)
ans+="/" + str;
return ans == "" ? "/" : ans;
}
Time complexity: O(n) where n is the size of given path