leetcode71:简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为 更加简洁的规范路径。

在 Unix 风格的文件系统中规则如下：

• 一个点 '.' 表示当前目录本身。
• 此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
• 任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
• 任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。

返回的 简化路径 必须遵循下述格式：

• 始终以斜杠 '/' 开头。
• 两个目录名之间必须只有一个斜杠 '/' 。
• 最后一个目录名（如果存在）不能 以 '/' 结尾。
• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

输入：path = "/home/"

输出："/home"

解释：

应删除尾随斜杠。

示例 2：

输入：path = "/home//foo/"

输出："/home/foo"

解释：

多个连续的斜杠被单个斜杠替换。

示例 3：

输入：path = "/home/user/Documents/../Pictures"

输出："/home/user/Pictures"

解释：

两个点 ".." 表示上一级目录（父目录）。

示例 4：

输入：path = "/../"

输出："/"

解释：

不可能从根目录上升一级目录。

示例 5：

输入：path = "/.../a/../b/c/../d/./"

输出："/.../b/d"

解释：

"..." 在这个问题中是一个合法的目录名。

提示：

• 1 <= path.length <= 3000
• path 由英文字母，数字，'.'，'/' 或 '_' 组成。
• path 是一个有效的 Unix 风格绝对路径。

步骤1：问题定义

输入：

• 一个字符串 path，表示 Unix 风格的绝对路径。

输出：

• 一个字符串，表示简化后的规范路径。

计算问题性质：

• 将输入的绝对路径字符串转换为一个简化的路径字符串，遵循 Unix 文件系统的规则。

限制条件：

• 输入字符串长度在 1 到 3000 之间。
• 字符串由英文字母、数字、‘.’、‘/’ 或 ‘_’ 组成。
• 字符串是一个有效的 Unix 风格绝对路径。

边界条件：

• 输入路径可能以 ‘/’ 结尾，需要处理。
• 输入路径可能包含多个连续的 ‘/’，需要合并。
• 输入路径可能包含 ‘.’ 或 ‘…’，需要根据规则处理。
• 输入路径可能为空或仅包含 ‘/’。

步骤2：解题步骤

1. 将输入路径按照 ‘/’ 分割成多个部分。
2. 遍历分割后的部分，忽略空字符串和 ‘.’。
3. 遇到 ‘…’ 时，如果栈不为空，则弹出栈顶元素（返回上一级目录）。
4. 将非 ‘.’ 和 ‘…’ 的部分压入栈中。
5. 将栈中的元素连接成字符串，每个元素之间用 ‘/’ 分隔。
6. 如果栈为空，返回根目录 ‘/’。

算法设计思路：

• 使用栈来处理路径的层级结构，因为栈的后进先出特性符合目录的上下级关系。

时间复杂度：O(n)，其中 n 是输入路径的长度，因为每个字符最多被处理两次（分割和压栈/弹栈）。 空间复杂度：O(n)，最坏情况下栈中可能包含所有分割后的部分。

步骤3：C++ 代码实现

步骤4：启发

• 使用栈处理具有层级结构的数据是一种常见且有效的方法。
• 在处理字符串问题时，可以使用 istringstream 和 getline 方便地分割字符串。
• 算法的优化可以考虑减少不必要的字符串操作，例如直接在输入字符串上操作，而不是创建多个字符串副本。

步骤5：实际应用

应用场景：文件系统路径解析

• 在文件系统中，用户输入的路径需要被解析并转换为实际的文件或目录路径。
• 例如，在开发文件浏览器或命令行工具时，用户可能输入复杂的路径字符串，程序需要将其简化并定位到正确的文件或目录。

具体实现：

• 在文件浏览器中，用户输入的路径字符串通过 simplifyPath 函数处理后，可以用来导航到正确的文件或目录。
• 在命令行工具中，简化后的路径可以用于执行文件操作，如复制、移动或删除文件。