0071. 简化路径【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 栈

1. 📝 题目描述

• leetcode

给你一个字符串 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 风格绝对路径。

2. 🎯 s.1 - 栈

c

char* simplifyPath(char* path) {
    int len = strlen(path);
    char** stack = (char**)malloc(sizeof(char*) * len);
    int top = 0;

    char* token = strtok(path, "/");
    while (token) {
        if (strcmp(token, "..") == 0) {
            if (top > 0) top--; // 返回上一级
        } else if (strcmp(token, ".") != 0 && strlen(token) > 0) {
            stack[top++] = token; // 有效目录名入栈
        }
        token = strtok(NULL, "/");
    }

    char* result = (char*)malloc(sizeof(char) * (len + 1));
    result[0] = '\0';
    if (top == 0) {
        strcat(result, "/");
    } else {
        for (int i = 0; i < top; i++) {
            strcat(result, "/");
            strcat(result, stack[i]);
        }
    }
    free(stack);
    return result;
}

js

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function (path) {
  const stack = []
  for (const part of path.split('/')) {
    if (part === '..') {
      stack.pop() // 返回上一级
    } else if (part && part !== '.') {
      stack.push(part) // 有效目录名入栈
    }
  }
  return '/' + stack.join('/')
}

py

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for part in path.split('/'):
            if part == '..':
                if stack: stack.pop()  # 返回上一级
            elif part and part != '.':
                stack.append(part)  # 有效目录名入栈
        return '/' + '/'.join(stack)

• 时间复杂度：$O(n)$，其中 n 是字符串 path 的长度
• 空间复杂度：$O(n)$，栈最多存储所有目录名

算法思路：

• 以 '/' 为分隔符拆分路径，逐段处理：
  • ".." → 栈非空则弹出栈顶（返回上级）
  • "." 或空串 → 跳过
  • 其余 → 有效目录名，入栈
• 最后将栈中元素用 '/' 拼接，加上前缀 '/' 即为简化路径