Medium

题目描述

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

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

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

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

示例 1：

输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：

输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

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

提示：

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

解题思路

解题思路

这是一个经典的路径解析问题，需要处理 Unix 风格路径中的特殊字符和规则。核心思想是使用栈来模拟目录层级的变化。

算法步骤：

  1. 分割路径：按照斜杠 '/' 分割路径，得到各个目录名
  2. 逐个处理目录名：
    • 空字符串或 "." ：忽略（表示当前目录）
    • ".." ：如果栈不为空，弹出栈顶元素（返回上级目录）
    • 其他有效目录名：压入栈中
  3. 构建结果：将栈中的目录名用斜杠连接，如果栈为空则返回根目录 "/"

关键处理：

  • 多个连续斜杠会产生空字符串，需要跳过
  • 在根目录时遇到 ".." 不能再向上，保持在根目录
  • 最终路径不以斜杠结尾（根目录除外）
  • "..." 等多个点的情况被视为有效目录名

时间复杂度 O(n)，空间复杂度 O(n)，其中 n 是路径长度。这种基于栈的解法是处理此类嵌套结构问题的标准方法。

代码实现

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> stack;
        string dir = "";
        
        for (int i = 0; i < path.length(); i++) {
            if (path[i] == '/') {
                if (!dir.empty()) {
                    if (dir == "..") {
                        if (!stack.empty()) {
                            stack.pop_back();
                        }
                    } else if (dir != ".") {
                        stack.push_back(dir);
                    }
                    dir = "";
                }
            } else {
                dir += path[i];
            }
        }
        
        // 处理最后一个目录名
        if (!dir.empty()) {
            if (dir == "..") {
                if (!stack.empty()) {
                    stack.pop_back();
                }
            } else if (dir != ".") {
                stack.push_back(dir);
            }
        }
        
        if (stack.empty()) {
            return "/";
        }
        
        string result = "";
        for (const string& s : stack) {
            result += "/" + s;
        }
        
        return result;
    }
};

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        components = path.split('/')
        
        for component in components:
            if component == '' or component == '.':
                # 空字符串或当前目录，忽略
                continue
            elif component == '..':
                # 返回上级目录
                if stack:
                    stack.pop()
            else:
                # 有效的目录名
                stack.append(component)
        
        # 构建简化路径
        return '/' + '/'.join(stack)

public class Solution {
    public string SimplifyPath(string path) {
        var stack = new Stack<string>();
        var components = path.Split('/');
        
        foreach (var component in components) {
            if (string.IsNullOrEmpty(component) || component == ".") {
                // 空字符串或当前目录，忽略
                continue;
            } else if (component == "..") {
                // 返回上级目录
                if (stack.Count > 0) {
                    stack.Pop();
                }
            } else {
                // 有效的目录名
                stack.Push(component);
            }
        }
        
        if (stack.Count == 0) {
            return "/";
        }
        
        var result = new StringBuilder();
        var dirs = new string[stack.Count];
        var index = stack.Count - 1;
        
        while (stack.Count > 0) {
            dirs[index--] = stack.Pop();
        }
        
        foreach (var dir in dirs) {
            result.Append("/").Append(dir);
        }
        
        return result.ToString();
    }
}

var simplifyPath = function(path) {
    const stack = [];
    const parts = path.split('/');
    
    for (const part of parts) {
        if (part === '' || part === '.') {
            continue;
        } else if (part === '..') {
            if (stack.length > 0) {
                stack.pop();
            }
        } else {
            stack.push(part);
        }
    }
    
    return '/' + stack.join('/');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历路径中的每个字符一次，其中 n 是路径长度
空间复杂度O(n)最坏情况下栈中存储所有的目录名，空间占用与路径长度成正比