[LeetCode 71] Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,

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

click to show corner cases.

Corner Cases: 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".

分析： 可以利用栈，碰到正常路径压入栈中，碰到/.不作任何操作，碰到/..删除栈顶元素。 下面代码中用数组来模拟栈：

class Solution { public: string simplifyPath(string path) { int len = path.size(); vector vec; int i = 0, index = 0; while(i < len){ int j = path.find('//', i + 1); string tmp; if(j != string::npos) tmp = path.substr(i, j - i); else {tmp = path.substr(i, len); j = len;}

        if(tmp == "/");
        else if(tmp == "/.");
        else if(tmp == "/..")
            {if(!vec.empty()) vec.pop_back();}
        else
            vec.push_back(tmp);
        i = j;
    }
    if(vec.empty()) return "/";
    else{
        string res;
        for(int i = 0; i < vec.size(); i++)
            res += vec[i];
        return res;
    }
}

};

思路： Unix的path规则可以在这里了解： http://en.wikipedia.org/wiki/Path_(computing)

归下类的话，有四种字符串：

1. "/"：为目录分隔符，用来分隔两个目录。
2. "."：当前目录
3. ".."：上层目录
4. 其他字符串：目录名

简化的核心是要找出所有的目录，并且如果遇到".."，需要删除上一个目录。

class Solution { public: string simplifyPath(string path) { string ret, curDir; vector allDir;

    path.push_back('/');
    for(int i = 0; i < path.size(); i++) {
        if(path[i]=='/') {
            if(curDir.empty()) continue;
            else if(curDir==".") {
                curDir.clear();
            }
            else if(curDir=="..") {
                if(!allDir.empty())
                    allDir.pop_back();
                curDir.clear();
            }
            else {
                allDir.push_back(curDir);
                curDir.clear();
            }
        }
        else {
            curDir.push_back(path[i]);
        }
    }

    for(int i = 0; i < allDir.size(); i++)
        ret.append("/" + allDir[i]);
    if(ret.empty()) ret = "/";
    return ret;
}

};