LeetCode 71. 简化路径

约 4 分钟
文章信息 13 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 面试经典 150 题 腾讯 字节 阿里 华为 拼多多 快手 猿辅导
标签
字符串 栈

题目描述

✅ 71. 简化路径

image-20260928204956441

image-20260928204956444

image-20260928204956445

题意分析

输入是以 / 开头的 Unix 风格绝对路径，要求按题目规则化简成规范路径。多个连续斜杠视为一个，完整片段 . 表示停在当前目录，完整片段 .. 表示返回父目录，根目录不能继续向上。

输出必须以一个 / 开头，目录之间只保留一个 /，除根目录外不以斜杠结尾。只有完整的 .、.. 才是特殊片段，其他包含点的名称都要作为普通名称保留；本题只处理路径字符串，无需访问文件系统。

解法：栈模拟目录进出

核心思路

[!blue]

返回父目录，就是撤销最近一次尚未被撤销的有效目录进入操作，正好符合栈的后进先出特点。按 / 分段后，用栈从底到顶保存当前从根目录出发的有效目录顺序。

每个片段只属于三种情况：空片段或 . 不改变当前位置，直接跳过；.. 在栈非空时弹出最后一个目录，空栈时保持在根目录；其余片段表示进入一个普通目录，追加到栈尾。

处理完任意路径前缀后，栈都表示该前缀对应的规范目录链。继续读一个片段只需根据上述规则更新最后一层，已经抵消的目录不必保留，也不会影响后面的处理。

最后按栈底到栈顶的顺序用 / 连接目录名，再统一补上开头的 /。栈里不存分隔符，拼接时自然不会产生连续斜杠或尾斜杠；空栈拼接后也正好得到根目录 /。

解题步骤

  1. 按 / 切分路径，创建保存有效目录名的栈。
  2. 遇到空片段或完整的 . 时跳过。
  3. 遇到完整的 .. 时，栈非空就移除末尾目录，栈为空则不做处理。
  4. 其余片段作为普通目录名追加到栈尾。
  5. 从栈底到栈顶拼接目录，在开头加上 / 并返回。

代码实现

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();

        for (String part : path.split("/")) {
            if (part.isEmpty() || part.equals(".")) {
                continue;
            }

            if (part.equals("..")) {
                if (!stack.isEmpty()) {
                    // 回到上一级只删除最后保留的目录，根目录不能再向上。
                    stack.removeLast();
                }
            } else {
                stack.addLast(part);
            }
        }

        return "/" + String.join("/", stack);
    }
}

import "strings"

func simplifyPath(path string) string {
    stack := []string{}
    for _, part := range strings.Split(path, "/") {
        if part == "" || part == "." {
            continue
        }
        if part == ".." {
            if len(stack) > 0 {
                // 回到上一级只删除最后保留的目录，根目录不能再向上。
                stack = stack[:len(stack)-1]
            }
        } else {
            stack = append(stack, part)
        }
    }

    return "/" + strings.Join(stack, "/")
}

复杂度分析

设路径字符串长度为 $n$。

  • 时间复杂度：$O(n)$。切分、比较片段和拼接的总字符处理量为线性，每个目录最多入栈、出栈一次。
  • 辅助空间复杂度：$O(n)$，切分结果和目录栈的规模均不超过输入长度。

关键点总结

[!green]

  • 栈维护当前有效目录链，.. 只撤销末尾的一层。
  • 根目录由空栈表示，向上操作不能再弹出任何内容。
  • 特殊含义根据完整片段判断，输出分隔符在最后统一添加。

易错点总结

[!yellow]

  • 弹栈前必须判空，根目录上的 .. 应被忽略，不能越界。
  • 不能用“以点开头”识别特殊片段，只有完整的 . 和 .. 才改变导航行为。
  • 空片段不应入栈，否则连续斜杠会被错误保留。
  • 目录输出顺序是栈底到栈顶，不能通过连续弹栈倒序拼接。
  • 空栈对应根目录 /，不能返回空字符串；普通路径也不能再追加尾斜杠。

相似题目

题目 难度 关联与区别
388. 文件的最长绝对路径 中等 同样解析目录层级，本题通过栈处理点目录与父目录，原题通过缩进层级累计文件路径长度。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/27525398
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！