C++ Coding Exercise – How to Simplify Path?

Simplify an absolute path for a file (Unix-style): For example,

path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Did you consider the case where path = “/../”?
In this case, you should return “/”.
Another corner case is the path might contain multiple slashes ‘/’ together, such as “/home//foo/”.
In this case, you should ignore redundant slashes and return “/home/foo”.

Submit your solution at: https://leetcode.com/problems/simplify-path/

Split the String

The best way is to first split the path by the delimiter / and ignore empty substrings:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

vector<string> split(string path, char d) {
    vector<string> r;
    int j = 0;
    for (int i = 0; i < path.length(); i ++) {
        if (path[i] == d) {
            string cur = path.substr(j, i - j);
            if (cur.length()) {
                r.push_back(cur);
            }
            j = i + 1; // start of next match
        }
    }
    if (j < path.length()) {
        r.push_back(path.substr(j));
    }
    return r;
}

vector<string> split(string path, char d) {
    vector<string> r;
    int j = 0;
    for (int i = 0; i < path.length(); i ++) {
        if (path[i] == d) {
            string cur = path.substr(j, i - j);
            if (cur.length()) {
                r.push_back(cur);
            }
            j = i + 1; // start of next match
        }
    }
    if (j < path.length()) {
        r.push_back(path.substr(j));
    }
    return r;
}

Push and Pop

As C++ Stack does not have iterator, we can use C++ vector instead. We can push_back and pop_back to emulate the stack operations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

string simplifyPath(string path) {
    vector<string> ps = split(path, '/');
    string p = "";
    vector<string> st;
    for (int i = 0; i < ps.size(); i ++) {
        if (ps[i] =="..") {
            if (st.size() > 0) {
                st.pop_back();
            }
        } else if (ps[i] != ".") {
            st.push_back(ps[i]);
        }
    }
    for (int i = 0; i < st.size(); i ++ ) {
        p += "/" + st[i];
    }
    return p.length() ? p : "/";
}

string simplifyPath(string path) {
    vector<string> ps = split(path, '/');
    string p = "";
    vector<string> st;
    for (int i = 0; i < ps.size(); i ++) {
        if (ps[i] =="..") {
            if (st.size() > 0) {
                st.pop_back();
            }
        } else if (ps[i] != ".") {
            st.push_back(ps[i]);
        }
    }
    for (int i = 0; i < st.size(); i ++ ) {
        p += "/" + st[i];
    }
    return p.length() ? p : "/";
}

The trailing slash should be removed. The multiple slashes should be removed as well. When we meet a single dot (meaning the current directory), we ignore it. If we meet double dots, we pop an folder from the stack, otherwise, we push to the stack.

–EOF (The Ultimate Computing & Technology Blog) —