path simplification algorithm

Topics

• string algorithms
• stacks

Problem Statement

Given an absolute file path in a Unix-style file system, simplify it by converting ”..” to the previous directory and removing any ”.” or multiple slashes. The resulting string should represent the shortest absolute path.

string simplifyPath(string path) {
  stack<string> st;
  vector<string> tokens = split(path, '/');
 
  for (string &token : tokens) {
    if (token == "." or token == "") {
      continue;
    }
 
    if (token == "..") {
      if (!st.empty())
        st.pop();
      continue;
    }
    st.push(token);
  }
 
  string res = "";
  while (!st.empty()) {
    res = "/" + st.top() + res;
    st.pop();
  }
  return res.empty() ? "/": res;
}

The algorithm is straightforward. It splits based on ”/” to obtain the tokens and for ”..” we make sure to pop out the prev token (if exists).

Note

The split() function used above can be implemented using find or stringstream.

T.C: $O(n)$
S.C: $O(n)$

Related