掌握Unix路径简化：五种有效算法比较【python力扣71题】

题目描述

给你一个字符串 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("/../"))    # 输出: "/"

不同算法的优劣势对比

应用示例

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

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

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