作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级

题目描述

给你一个字符串 path，表示一个 Unix 风格的绝对路径，请你简化它并返回。

Unix 风格的绝对路径中，.. 表示返回上一级目录，. 表示当前目录。简化路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，简化的路径必须是表示绝对路径的最短字符串。

输入格式

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

输出格式

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

示例

示例 1

输入: path = "/home/"
输出: "/home"
解释: "/home" 和 "/." 本质上是一样的，前者是简化的路径。

示例 2

输入: path = "/../"
输出: "/"
解释: "/../" 将会移到根目录。

---

方法一：使用栈

解题步骤

1. 分割路径：使用 / 将路径分割成部分。
2. 处理每部分：使用栈来处理每一部分。
   • 如果是 ..，则弹出栈（如果栈不为空）。
   • 如果是有效的路径名（非空且不是 .），则压入栈。
3. 构建最终路径：从栈中弹出所有元素来构建最终的路径。

完整的规范代码

def simplifyPath(path):
    """
    使用栈简化 Unix 风格的绝对路径
    :param path: str, 输入的 Unix 风格路径
    :return: str, 简化后的路径
    """
    stack = []
    parts = path.split('/')
    for part in parts:
        if part == '..':
            if stack:
                stack.pop()
        elif part and part != '.':
            stack.append(part)
    return '/' + '/'.join(stack)

# 示例调用
print(simplifyPath("/home/"))  # 输出: "/home"
print(simplifyPath("/../"))    # 输出: "/"

算法分析

• 时间复杂度：(O(n))，其中 n 是路径的长度。
• 空间复杂度：(O(n))，使用了栈来存储路径的各个部分。

方法二：直接解析

解题步骤

1. 遍历和解析：直接在遍历过程中处理路径。
2. 应用路径规则：同方法一，直接处理和压栈。

完整的规范代码

def simplifyPath(path):
    """
    直接解析路径以简化 Unix 风格的绝对路径
    :param path: str, 输入的 Unix 风格路径
    :return: str, 简化后的路径
    """
    parts = path.split('/')
    stack = []
    for part in parts:
        if part == '..':
            if stack:
                stack.pop()
        elif part and part != '.':
            stack.append(part)
    return '/' + '/'.join(stack)

# 示例调用
print(simplifyPath("/home/"))  # 输出: "/home"
print(simplifyPath("/../"))    # 输出: "/"

方法三：递归

解题步骤

1. 定义递归函数：递归地处理路径，将路径分解为头部和尾部。
2. 递归简化：根据头部处理剩余的路径。

完整的规范代码

def simplifyPath(path):
    """
    使用递归简化 Unix 风格的绝对路径
    :param path: str, 输入的 Unix 风格路径
    :return: str, 简化后的路径
    """
    def recursive(parts):
        if not parts:
            return []
        part = parts.pop(0)
        if part == '..':
            return recursive(parts)
        elif part == '.' or not part:
            return recursive(parts)
        else:
            return [part] + recursive(parts)

    parts = path.split('/')
    result = recursive(parts)
    return '/' + '/'.join(result)

# 示例调用
print(simplifyPath("/home/"))  # 输出: "/home"
print(simplifyPath("/../"))    # 输出: "/"

方法四：正则表达式

解题步骤

1. 正则匹配：使用正则表达式来提取所有有效的路径部分。
2. 重建路径：根据提取的路径部分重建整个路径。

完整的规范代码

import re

def simplifyPath(path):
    """
    使用正则表达式简化 Unix 风格的绝对路径
    :param path: str, 输入的 Unix 风格路径
    :return: str, 简化后的路径
    """
    parts = re.findall(r'[^/]+', path)
    stack = []
    for part in parts:
        if part == '..':
            if stack:
                stack.pop()
        elif part != '.':
            stack.append(part)
    return '/' + '/'.join(stack)

# 示例调用
print(simplifyPath("/home/"))  # 输出: "/home"
print(simplifyPath("/../"))    # 输出: "/"

方法五：解析并反向处理

解题步骤

1. 反向解析：从路径末尾开始解析，使用栈处理逻辑。
2. 重建路径：根据处理结果重建路径。

完整的规范代码

def simplifyPath(path):
    """
    反向解析 Unix 风格的绝对路径
    :param path: str, 输入的 Unix 风格路径
    :return: str, 简化后的路径
    """
    parts = path.split('/')
    stack = []
    for part in reversed(parts):
        if part == '..':
            stack.append(part)
        elif part and part != '.':
            if stack and stack[-1] == '..':
                stack.pop()
            else:
                stack.append(part)
    stack.reverse()
    return '/' + '/'.join(filter(lambda x: x != '..', stack))

# 示例调用
print(simplifyPath("/home/"))  # 输出: "/home"
print(simplifyPath("/../"))    # 输出: "/"

不同算法的优劣势对比

特征	方法一：使用栈	方法二：直接解析	方法三：递归	方法四：正则表达式	方法五：解析并反向处理
时间复杂度	(O(n))	(O(n))	(O(n))	(O(n))	(O(n))
空间复杂度	(O(n))	(O(n))	(O(n))	(O(n))	(O(n))
优势	明确易懂，逻辑简单	同上，代码更简洁	递归思想，简洁	正则清晰，易维护	可处理复杂情况，灵活
劣势	需要额外空间	需要处理特殊情况	可能栈溢出	可能慢于其他方法	实现稍复杂

应用示例

文件系统工具：在开发文件系统工具（如文件浏览器或命令行工具）时，路径的解析和简化是一个常见需求。例如，在实现 cd 命令或显示当前路径时，需要将用户输入的路径转换为标准化的绝对路径。

Web服务器：在处理静态文件请求时，需要从 URL 中解析出相对路径，并将其转换为服务器上的绝对路径。使用这些方法可以防止路径遍历攻击，确保服务器的安全。

通过选择适合的路径解析算法，可以提高软件的性能和安全性，同时提供更好的用户体验。