【面试经典150 | 栈】简化路径

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：字符串数组模拟栈
其他语言
- python3
写在最后

Tag

【栈】【字符串】

题目来源

71. 简化路径

题目解读

将 Unix 风格的绝对路径转化成更加简洁的规范路径。字符串中会出现 字母、数字、/、_、. 和 .. 这几种字符，其中 . 表示当前目录本身，.. 表示将目录切换到上一级目录。

最后返回的 规范路径 必须满足以下几个要求：

必须以斜杠 / 开头；
两个目录名之间必须只有一个 /；
最后一个路径名之后不能以 / 结尾；
需要将路径字符串中的 . 和 .. 转到对应的路径输出。

解题思路

方法一：字符串数组模拟栈

对于本题，表示绝对路径的字符串中的目录名或者目录操作（. 和 ..）都位于 / 之间，因此我们可以先根据分隔符 / 来分割字符串，得到目录名和目录操作。对应的 C++ 代码如下：

vector<string> split(string& ss, char delim) {
    /*
    * 以字符 delim 分割字符串 ss，字符串数组中可能会出现空字符串
    */
    vector<string> res; 
    string str;
    for (auto s : ss) {
        if (s == delim) {
            res.push_back(str);
            str = "";
        }
        else {
            str += s;
        }
    }
    res.push_back(str); // 防止 ss 最后一个字符不是分隔时丢掉最后一个字符串
    return res;
}

以上代码表示根据分隔符 delim 来分割字符串 ss，将分割后的字符串存放到数组中。

在绝对路径中可能会存在多个连续的 /，那么经过 split() 分割代码分割后的字符串数组中可能会出现空字符串，这一点需要注意，后续在遍历字符串数组时不需要处理空字符。

有了目录名和目录操作之后，我们就可以根据目录名和目录操作对目录进行操作生成简洁的规范路径了。因为在路径操作中会返回上一级目录，这里有一种 “先进后出” 的特性，所以使用栈这种基本的数据结构来存储目录名（遇到 ..，我们就弹出当前的栈顶元素，新漏出来的字符串就是当前的目录）。简化路径之后，我们还需要将栈中的所有目录名使用 / 连接起来，这一步骤需要从栈底到栈顶的顺序遍历栈中目录，因此为了方便遍历操作，使用字符串数组模拟栈。

选定了基本的数据结构之后，我们就可以遍历字符串数组：

如果当前的字符串为 ..，并且栈非空，那么我们就要弹出栈顶元素，模拟返回上一级目录；
否则，如果当前的字符串非空，并且不为 .，那么就将当前的目录名加入栈中。

遍历结束后，我们将栈中目录使用 / 拼接得到简洁的规范路径 res：

如果栈为空，res = "/"；
否则，枚举栈中目录名 str，更新 res += "/" + str；
最后返回 res。

实现代码

class Solution {
public:
    vector<string> split(string& ss, char delim) {
        /*
        * 以字符 delim 分割字符串 ss，字符串数组中可能会出现空字符串
        */
        vector<string> res; 
        string str;
        for (auto s : ss) {
            if (s == delim) {
                res.push_back(str);
                str = "";
            }
            else {
                str += s;
            }
        }
        res.push_back(str); // 防止 ss 最后一个字符不是分隔时丢掉最后一个字符串
        return res;
    }

    string simplifyPath(string path) {
        vector<string> names = split(path, '/');
        vector<string> stk;
        for (string& name : names) {
            // 遇到 ".." 切换到上一级目录
            if (name == "..") {
                if (!stk.empty()) {
                    stk.pop_back();
                }
            }
            // 遇到目录名加入栈
            else if (!name.empty() && name != ".") {
                stk.push_back(name);
            }
        }

        // 将栈中的目录以 '/' 作为分隔，包装起来
        string res;
        if (stk.empty()) {
            res = "/";
        }
        else {
            for (string& str : stk) {
                res += "/" + str;
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度： $O (n)$ ， $n$ 是字符串 path 的长度。

空间复杂度： $O (n)$ ，需要 $O (n)$ 的空间存储 names 中的所有字符串。

其他语言

python3

class Solution:
    def simplifyPath(self, path: str) -> str:
        names = path.split("/")
        stack = list()
        for name in names:
            if name == "..":
                if stack:
                    stack.pop()
            elif name and name != ".":
                stack.append(name)
        return "/" + "/".join(stack)