0071. Simplify Path
===================
题目信息
--------
:题号: 0071. 简化路径
:难度: Medium
:主题: 字符串、栈、路径规范化
:原题: `LeetCode 0071 `_
:重点: 从按斜杠分段,推导到维护规范目录栈,再用写入位置完成结果回滚
题目重述
--------
给定一个以 ``/`` 开头的 Unix 风格绝对路径 ``path``,返回对应的规范路径。
路径中的组件遵循以下规则:
* 连续多个 ``/`` 只表示一个分隔位置;
* 空组件和 ``.`` 不改变当前目录;
* ``..`` 返回父目录,但不能越过根目录;
* 其他非空组件都按普通目录名保留,包括 ``...``、``.git`` 和 ``name..``。
规范结果必须以一个 ``/`` 开头,目录之间只能有一个 ``/``,除根目录本身外不能以 ``/`` 结尾。
约束条件:
* ``1 <= path.length <= 3000``;
* 路径由英文字母、数字、点、斜杠和下划线组成。
自建示例
--------
* 混合规则:``/team//docs/./draft/../final/`` 规范化为 ``/team/docs/final``;
* 根目录回退:``/../../a`` 规范化为 ``/a``,前两个 ``..`` 都不能越过根目录;
* 点组成的名称:``/a/.../.hidden/..`` 规范化为 ``/a/...``,``...`` 是普通目录名;
* 全部抵消:``/a/b/../..`` 规范化为 ``/``;
* 只有分隔符:``////`` 规范化为 ``/``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
std::string buildPath(const std::vector& directories) {
if (directories.empty()) {
return "/";
}
std::string result;
for (const std::string& directory : directories) {
result.push_back('/');
result += directory;
}
return result;
}
std::string splitWithStream(const std::string& path) {
std::stringstream stream(path);
std::string component;
std::vector directories;
while (std::getline(stream, component, '/')) {
if (component.empty() || component == ".") {
continue;
}
if (component == "..") {
if (!directories.empty()) {
directories.pop_back();
}
} else {
directories.push_back(component);
}
}
return buildPath(directories);
}
std::string manualComponentScan(const std::string& path) {
std::vector directories;
int index = 0;
const int length = static_cast(path.size());
while (index < length) {
while (index < length && path[index] == '/') {
++index;
}
const int start = index;
while (index < length && path[index] != '/') {
++index;
}
if (start == index) {
continue;
}
const std::string component = path.substr(start, index - start);
if (component == ".") {
continue;
}
if (component == "..") {
if (!directories.empty()) {
directories.pop_back();
}
} else {
directories.push_back(component);
}
}
return buildPath(directories);
}
std::string rollbackBuffer(const std::string& path) {
std::string result;
std::vector restorePositions;
int index = 0;
const int length = static_cast(path.size());
while (index < length) {
while (index < length && path[index] == '/') {
++index;
}
const int start = index;
while (index < length && path[index] != '/') {
++index;
}
if (start == index) {
continue;
}
const std::string component = path.substr(start, index - start);
if (component == ".") {
continue;
}
if (component == "..") {
if (!restorePositions.empty()) {
result.resize(restorePositions.back());
restorePositions.pop_back();
}
} else {
restorePositions.push_back(static_cast(result.size()));
result.push_back('/');
result += component;
}
}
return result.empty() ? "/" : result;
}
public:
std::string simplifyPath(std::string path) {
return manualComponentScan(path);
}
};
题解
----
组件级语义
~~~~~~~~~~
路径规则作用于两个斜杠之间的完整组件,而不是任意字符片段。``.`` 和 ``..`` 只有在组件完全相等时才有特殊语义;
``...``、``.hidden`` 和 ``name..`` 都必须保留。
因此,反复替换 ``//``、``/./`` 或某段 ``name/..`` 并不稳妥。字符串替换既可能误判普通名称,也会反复移动后续字符。
更直接的模型是先识别组件,再按组件类别更新当前目录层级。
目录栈不变量
~~~~~~~~~~~~
处理完输入的任意前缀后,``directories`` 从底到顶恰好保存该前缀规范化后的目录层级:
* 空组件和 ``.`` 不改变栈;
* 普通组件表示进入子目录,压入栈顶;
* ``..`` 表示返回父目录,栈非空时弹出栈顶;
* 栈为空时已经位于根目录,额外的 ``..`` 不产生效果。
以 ``/team//docs/./draft/../final/`` 为例:
.. list-table::
:header-rows: 1
* - 组件
- 处理后目录栈
- 动作
* - ``team``
- ``[team]``
- 进入目录
* - ``docs``
- ``[team, docs]``
- 进入目录
* - ``.``
- ``[team, docs]``
- 保持当前位置
* - ``draft``
- ``[team, docs, draft]``
- 进入目录
* - ``..``
- ``[team, docs]``
- 返回父目录
* - ``final``
- ``[team, docs, final]``
- 进入目录
输入组件按顺序更新栈,因此当前栈始终对应已经处理部分的唯一规范路径。
流式分词
~~~~~~~~
``splitWithStream`` 使用 ``std::getline`` 按 ``/`` 分段。连续斜杠会产生空组件,统一忽略即可。
这一版直接表达了“分段后分类”的思路,但会创建流对象,并把分词过程交给通用字符串流。算法仍为线性时间,额外抽象并非本题所必需。
手工组件扫描
~~~~~~~~~~~~
``manualComponentScan`` 用下标直接识别每个组件:
#. 跳过一段连续斜杠;
#. 记录组件起点 ``start``;
#. 扫描到下一个斜杠或字符串末尾;
#. 对半开区间 ``[start, index)`` 对应的组件执行栈操作。
每个输入字符只被跳过或扫描常数次。连续斜杠、开头斜杠和结尾斜杠都由同一循环处理,不需要额外分支。
结果重建
~~~~~~~~
栈内只含真实目录名。重建时为每个目录先写入一个 ``/``,再写目录名:
.. code-block:: text
[team, docs, final] -> /team/docs/final
这种写法自动保证目录之间只有一个斜杠,并且不会产生尾斜杠。若栈为空,单独返回根目录 ``/``。
写入位置回滚
~~~~~~~~~~~~
``rollbackBuffer`` 不保存目录字符串,而是在结果中直接追加 ``/组件``。追加前记录当前结果长度;遇到 ``..`` 时,
将结果缩回最近一次记录的位置,就等价于删除最后一级目录。
例如结果已经是 ``/team/docs``,追加 ``/draft`` 前记录长度 ``10``。之后读取 ``..``,把字符串恢复到长度
``10``,结果重新变为 ``/team/docs``。
目录栈保存的是“有哪些目录”,写入位置栈保存的是“删除最后一级时应退到哪里”。两者表达同一个后进先出的结构。
正确性
~~~~~~
对输入组件按顺序归纳:
* 空组件和 ``.`` 不改变当前位置,忽略后结果不变;
* 普通组件唯一地在当前路径末尾增加一级目录,压栈后结果正确;
* ``..`` 在非根目录删除最后一级,在根目录保持不动,恰好符合父目录规则。
因此全部组件处理完成后,栈表示的目录层级与原路径指向的位置相同。重建过程只插入必要的单个斜杠,所得字符串同时满足
路径语义和规范格式。
复杂度分析
~~~~~~~~~~
设路径长度为 ``n``:
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 主要状态
* - 流式分词
- ``O(n)``
- ``O(n)``
- 字符串流与目录栈
* - 手工组件扫描
- ``O(n)``
- ``O(n)``
- 目录栈
* - 写入位置回滚
- ``O(n)``
- ``O(n)``
- 结果缓冲区与恢复位置栈
返回字符串本身最多包含 ``O(n)`` 个字符。公开入口采用手工组件扫描,它不依赖流对象,组件边界和栈更新也最直接。
边界处理
~~~~~~~~
* 输入为 ``/`` 或全部由斜杠组成时,目录栈为空,返回 ``/``;
* 任意多个前导 ``..`` 都不能让空栈继续弹出;
* ``.`` 和 ``..`` 之外的点组成名称全部保留;
* 结尾斜杠只产生空组件,不会进入结果;
* 每个目录名按原字符完整保留,算法不修改大小写或内容。