LeetCode 71. 简化路径

发布时间：2020-12-15 23:24:31 所属栏目：安全来源：网络整理

导读：给定一个文档 (Unix-style) 的完全路径，请进行路径简化。例如， path?=? "/home/" ,=? "/home" path?=? "/a/./b/../../c/" ,=? "/c" 边界情况: 你是否考虑了路径 =? "/../" ?的情况？在这种情况下，你需返回? "/" ?。此外，路径中也可能包含多个斜杠?

给定一个文档 (Unix-style) 的完全路径，请进行路径简化。

例如，
path?=?"/home/",=>?"/home"
path?=?"/a/./b/../../c/",=>?"/c"

边界情况:

你是否考虑了路径 =?"/../"?的情况？
在这种情况下，你需返回?"/"?。
此外，路径中也可能包含多个斜杠?‘/‘?，如?"/home//foo/"?。
在这种情况下，你可忽略多余的斜杠，返回?"/home/foo"?。

首先应该明确，"."和".."都是目录。因此，适合将/作为分隔符，将目录全部分开。为了方便，总是使得路径最后一个字符为‘/‘。如果是这样做的话，需要注意栈为空的情况。

class Solution {
public:
    string simplifyPath(string path) {
        stack<string> s;
        if(path.size() > 1 && path.back() != ‘/‘) {
            path.push_back(‘/‘);
        }
        for(int i = 0; i < path.size(); ) {
            while(i < path.size() && path[i] == ‘/‘) {
                i++;
            }
            int j = i + 1;
            while(j < path.size() && path[j] != ‘/‘) {
                j++;
            }
            //[i,j),j是第一个/
            string cur = path.substr(i,j - i);
            if(cur == "..") {
                if(!s.empty()) {
                    s.pop();
                }
            } else if(cur == "") {
                break;
            } else if(cur != ".") {
                s.push(cur);
            }
            i = j;
        }
        string res;
        while(!s.empty()) {
            res.insert(0,"/" + s.top());
            s.pop();
        }
        return res == ""? "/": res;
    }
};

另一种使用getline的方法更清晰：

class Solution {
public:
    string simplifyPath(string path) {
        string res,tmp;
        vector<string> stk;
        stringstream ss(path);
        while(getline(ss,tmp,‘/‘)) {        //  用/作为分隔符(默认是换行符,第三个参数为自定义的分隔符)
            if (tmp == "" || tmp == ".") continue;
            if (tmp == ".." && !stk.empty()) 
                stk.pop_back();
            else if (tmp != "..")
                stk.push_back(tmp);
        }
        for(auto str : stk) res += "/"+str;
        return res.empty() ? "/" : res;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!