LeetCode 71. 简化路径

Categories:

题目描述
思路分析
1. 解法一：栈模拟（推荐）
相似题目

题目描述

✅ 71. 简化路径

思路分析

解法一：栈模拟（推荐）

核心思路：

将路径按 "/" 分割成各个部分，逐一处理每个片段。

遇到空串或 "." 时，跳过（原地不动）。

遇到 ".." 时，若栈非空则弹出栈顶（回到上一级目录）。

遇到有效目录名时，压入栈中。

最终将栈中元素从底到顶用 "/" 拼接，并在开头加 "/"。

复杂度分析：

时间复杂度：O(n)，其中 n 表示路径字符串的长度，分割与遍历各片段的总时间为线性。

空间复杂度：O(n)，其中 n 表示路径字符串的长度，栈最多存储所有有效目录名。

class Solution {
    public String simplifyPath(String path) {
        // 按 "/" 分割路径
        String[] parts = path.split("/");
        Deque<String> stack = new ArrayDeque<>();

        for (String part : parts) {
            // 跳过空串和当前目录符号 "."
            if (part.isEmpty() || part.equals(".")) {
                continue;
            }
            // 遇到 ".." 时回到上一级目录
            if (part.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }
            } else {
                // 有效目录名压栈
                stack.offerLast(part);
            }
        }

        // 将栈中元素拼接为规范路径
        StringBuilder sb = new StringBuilder();
        for (String dir : stack) {
            sb.append("/").append(dir);
        }

        return sb.length() > 0 ? sb.toString() : "/";
    }
}

func simplifyPath(path string) string {
    // 按 "/" 分割路径
    parts := strings.Split(path, "/")
    stack := make([]string, 0)

    for _, part := range parts {
        // 跳过空串和当前目录符号 "."
        if part == "" || part == "." {
            continue
        }
        // 遇到 ".." 时回到上一级目录
        if part == ".." {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]
            }
        } else {
            // 有效目录名压栈
            stack = append(stack, part)
        }
    }

    // 将栈中元素拼接为规范路径
    return "/" + strings.Join(stack, "/")
}

相似题目

题目	难度	考察点
20. 有效的括号	简单	栈、字符串
150. 逆波兰表达式求值	中等	栈、数学
224. 基本计算器	困难	栈、字符串
316. 去除重复字母	中等	栈、贪心、字符串
394. 字符串解码	中等	栈、字符串
682. 棒球比赛	简单	栈、模拟
1472. 设计浏览器历史记录	中等	栈、设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/27525398