Shorten Path

• Time : O(n)
• Space : O(n)

using namespace std;

string parse(string& s, int& p) {
    string res = "";
    while(p < s.length() and s[p] != '/') {
        res.push_back(s[p++]);
    }
    p++;
    return res;
}

string shortenPath(string path) {
    int i = 0;
    bool root = path[0] == '/';
    vector<string> st;
    while(i < path.length()) {
        auto dir = parse(path, i);
        if(dir == "." or dir == "") continue;
        else if(dir == "..") {
            if(root) {
                if(!st.empty()) st.pop_back();
            } else {
                if(!st.empty() and st.back() != "..") st.pop_back();
                else st.push_back(dir);
            }
        } else st.push_back(dir);
    }

    string res = "";
    for(auto& token : st)
        res += token + '/';
    if(res.length())
        res.pop_back();
    return root ? "/" + res : res;
}