P2581. 模拟目录管理

解题思路

系统设计的大模拟题，关键还是在于读懂题意。

对于目录的操作命令，一共有四种：创建新目录、进入已存在目录、返回上一级目录、打印当前路径。如果你使用过 Linux 系统，那么上述这些概念应当是相当熟悉的。

另外，对于文件路径类的问题，类似于 简化路径，我们可以用一个栈 path 来储存路径，一旦发生进入目录或者返回目录，则对应入栈和出栈操作。可以将 path 初始化为空。

目录树形结构

创建出来的目录系统呈现一个树形结构。那么我们只需要构建这样一个树形结构来对应整个目录系统，并根据操作命令进行相应操作即可。

节点类的设计

对于每一个文件夹所对应的节点，我们需要知道以下信息：

• 这个文件夹的名字（对应打印操作）
• 这个文件夹的父节点，即它的上一级文件夹对应的节点（对应返回操作）
• 这个文件夹的子节点构成的集合，即它所有的下一级文件夹对应的节点构成的集合（对应创建、进入操作）

由于信息较多，我们可以构建出如下的节点类：

要特别注意子节点构成的集合，需要构建成哈希表的形式，其中 key 为子文件名，value 为子文件对应的节点，也是一个 Node。这样做是为了方便后续的查找操作。

在整个动态模拟的过程中，我们需要知道根节点 root，还需要知道当前进入到了哪一个节点中，故需要一个当前节点 curNode，将其初始化为根节点 root。

代码框架

对于每一个操作 operations[i]，如果：

• 其为打印操作，那么存在 operations[i] == "pwd" 成立
• 其不为打印操作，那么其必然可以用空格给分割成两部分，即：

在进一步判断操作之前，可以判断文件名 fileName 本身是否存在嵌套。若其以 "/" 为分割符进行切割后，长度大于 1，说明存在文件嵌套的情况，这是一个无效命令，可以直接跳过。即：

若 fileName 是一个有效文件名，则可以进一步根据 op 判断操作类型。若该操作为：

• 创建操作，那么存在 op == "mkdir" 成立
• 进入操作，那么存在 op == "cd" 且 fileName != ".." 成立
• 退出操作，那么存在 op == "cd" 且 fileName == ".." 成立

故可以将整个模拟过程的代码框架封装在 solve() 函数中，具体如下：

打印操作

打印操作是最简单的。由于题目要求输出最后一条命令运行结果字符串，因此如果 operations 数组的最后一个元素不是打印操作，即 operations[-1] != "pwd"，则直接返回打印出 "/" 即可。

（照理来说应该返回空字符串 ""，但根据考试反馈，这种情况下必须返回 "/" 才是正确结果）

另外，如果在遍历过程中遇到打印操作，则直接跳过即可。

创建操作

创建操作要求在当前节点 curNode 下创建一个新文件夹，我们需要判断这个子文件名 fileName 是否已经存在于 curNode 的子节点中。若：

• 已存在，则无需重复创建，直接跳过
• 不存在，则创建新子文件对应的新节点，并且将其加入 curNode 的子节点集合中

进入操作

进入操作要求进入当前节点 curNode 下一个名为 fileName 的文件夹，我们需要判断这个子文件名 fileName 是否已经存在于 curNode 的子节点中。若：

• 不存在，则无法进入一个不存在的文件，直接跳过
• 已存在，则需要更新 curNode 为 fileName 对应的节点，同时也需要将 fileName 更新加入 path 中

返回操作

返回操作要求返回 curNode 节点的上一层节点，我们需要判断当前节点 curNode 是否为根节点 root。若：

• 是根节点，则无法再返回上一级，直接跳过
• 不是根节点，则我们可以通过 curNode 中的成员变量 curNode.father 来得到 curNode 的父节点，将 curNode 进行修改，同时也需要将 path 的最后一个元素（即 curNode 的文件名）弹出

最终结果

在做完 n-1 次遍历之后，最后一次操作是打印操作，此时我们需要将 path 中的结果进行合并，并且作为 solve() 函数的返回值。

我们需要判断 path 路径栈的长度，若：

• 长度为 0，则说明最终位于根节点，需要返回 "/"
• 长度不为 0，则需要将 path 中的所有字符串用 "/" 连接，并且前后还需要再加上两个 "/"，作为最终路径结果

复杂度分析 设命令条数为 n，单条命令（含目录名）的长度上界为 L。主循环对每条命令只处理一次：split 切割与「目录名是否含 / 」的检查是 O(L)；mkdir 与 cd 都是对当前节点的 children 哈希表做一次查找或插入，键为目录名，平均 O(L)（哈希需要读完整个名字）；cd .. 只是沿 father 指针回退并执行 path.pop()，O(1)。因此遍历全部命令的总时间为 O(n·L)，与输入总长度同阶。收尾用 join 拼接路径的代价与最终路径长度成正比，同样不超过 O(n·L)。空间方面，目录树的节点数最多等于成功执行的 mkdir 次数（不超过 n），每个节点存一个名字和一张子节点哈希表，加上路径栈 path 与暂存的 operations 列表，总空间 O(n·L)。整段算法没有嵌套遍历，瓶颈只是把每条命令各读一遍，属于线性复杂度。