题目描述

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径

请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

样例

示例 1：
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

示例 3：
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：
输入："/a/./b/../../c/"
输出："/c"

示例 5：
输入："/a/../../b/../c//.//"
输出："/c"

示例 6：
输入："/a//b////c/d//././/.."
输出："/a/b/c"

算法1

(模拟) $O(n)$

要考虑特殊处理的情况包括：
连续斜杠换成一个斜杠；
一个点的目录，忽略；
两个点的目录，向上找一层；
答案末尾不要以斜杠结尾；
空字符输出斜杠。

字符串模拟真难，每次写出来都又臭又长，呜呜。

时间复杂度

遍历字符串一次，且每个字符最多被加入再被弹出，所以是$O(n)$

参考文献

C++ 代码

class Solution {
public:    
    string simplifyPath(string path) {
        if (path.empty()) return "/";
        string res;
        int n = path.size(), i = 0;

        while (i < n){
            if (path[i] == '/'){
                while (i + 1 < n && path[i + 1] == '/') ++i; // 多余的斜杠不读入
                while (res.size() && res.back() == '/') res.pop_back(); // 规避读入多个斜杠的情况
                res.push_back(path[i++]);
            }

            else if (path[i] == '.'){
                int cnt = 0; string tmp;
                while (i < n && path[i] == '.') 
                    ++cnt, tmp.push_back(path[i++]); // 数一数有几个点

                if (cnt == 1 && (i >= n || path[i] == '/') && (res.empty() || res.back() == '/')) 
                    ++i; // 一个点，跳过
                else if (cnt == 2 && (i >= n || path[i] == '/') && (res.empty() || res.back() == '/')){ 
                    // 两个点，退路径
                    while (res.size() && res.back() == '/') res.pop_back();
                    while (res.size() && res.back() != '/') res.pop_back();
                    if (res.size()) res.pop_back();
                }
                else { // 其他情况，点是文件名中的字符，直接加
                    while (i < n && path[i] != '/') tmp.push_back(path[i++]);
                    res += tmp;
                }
            }

            else res.push_back(path[i++]);
        }

        while (res.size() && res.back() == '/') res.pop_back(); // 去掉末尾斜杠
        if (res.empty()) return "/"; // 如果是空字符串，返回斜杠
        return res;
    }
};

学一手y总的简洁实现

class Solution {
public:
    string simplifyPath(string path) {
        if (path.empty() || path.back() != '/') path += '/';

        string res, tmp;

        for (char c: path){
            if (c != '/') tmp += c;
            else{
                if (tmp == ".."){
                    while (res.size() && res.back() != '/') res.pop_back();
                    if (res.size()) res.pop_back();
                }
                else if (tmp != "." && tmp != "") res += "/" + tmp;
                tmp = "";
            }
        }

        if (res.empty()) return "/";
        return res;
    }
};