What is the key pattern for solving the Simplify Path problem?

The key pattern is stack-based state management, where each component of the path is processed and pushed onto a stack, with special handling for '..' to move up one directory.

How do you handle consecutive slashes in Simplify Path?

Consecutive slashes should be treated as a single slash, so when processing the path, consecutive slashes are ignored or collapsed into one.

What should happen if the input path is just '/'?

If the path is just '/', the output should be '/', representing the root directory of the file system.

How should '..' be handled in the Simplify Path problem?

The '..' should move up one level in the directory tree. If the current directory is the root, '..' should be ignored.

Can Simplify Path be solved with a different approach than stack-based management?

While the stack-based approach is optimal for managing state, alternative approaches like recursion or manual string manipulation can be used but may be less efficient.

#71

Medium

auto_awesome栈·状态

LeetCode 题解工作台

简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格绝对路径（以 '/' 开头），请你将其转化为更加简洁的规范路径。在 Unix 风格的文件系统中规则如下：一个点 '.' 表示当前目录本身。此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。任意多个连续的斜…

字符串栈

题目描述

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

在 Unix 风格的文件系统中规则如下：

一个点 '.' 表示当前目录本身。
此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。

返回的 简化路径 必须遵循下述格式：

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

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

示例 1：

输入：path = "/home/"

输出："/home"

解释：

应删除尾随斜杠。

示例 2：

输入：path = "/home//foo/"

输出："/home/foo"

解释：

多个连续的斜杠被单个斜杠替换。

示例 3：

输入：path = "/home/user/Documents/../Pictures"

输出："/home/user/Pictures"

解释：

两个点 ".." 表示上一级目录（父目录）。

示例 4：

输入：path = "/../"

输出："/"

解释：

示例 5：

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

输出："/.../b/d"

解释：

"..." 在这个问题中是一个合法的目录名。

提示：

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

lightbulb

解题思路

方法一：栈

我们先将路径按照 '/' 分割成若干个子串，然后遍历每个子串，根据子串的内容进行如下操作：

若子串为空，或者为 '.'，则不做任何操作，因为 '.' 表示当前目录；
若子串为 '..'，则需要将栈顶元素弹出，因为 '..' 表示上一级目录；
若子串为其他字符串，则将该子串入栈，因为该子串表示当前目录的子目录。

最后，我们将栈中的所有元素按照从栈底到栈顶的顺序拼接成字符串，即为简化后的规范路径。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为路径的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def simplifyPath(self, path: str) -> str:
        stk = []
        for s in path.split('/'):
            if not s or s == '.':
                continue
            if s == '..':
                if stk:
                    stk.pop()
            else:
                stk.append(s)
        return '/' + '/'.join(stk)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's ability to apply stack-based state management to a real-world path traversal problem.
question_mark
Assess how well the candidate handles edge cases like empty or root paths and redundant slashes.
question_mark
Check for clear and efficient processing of the path string and stack manipulation.

warning

常见陷阱

外企场景

error
Forgetting to handle consecutive slashes as a single slash, which can lead to incorrect paths.
error
Failing to correctly manage the '..' operation to navigate to the parent directory.
error
Not accounting for the path starting with a slash, which is an important aspect of an absolute path.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to handle relative paths in addition to absolute paths.
arrow_right_alt
Handle cases where the input path contains symbolic links or references to special directories like '/var'.
arrow_right_alt
Extend the problem to handle a file system with deeper nested directories.

help

常见问题

外企场景

继续练习

#32 最长有效括号 #20 有效的括号 #224 基本计算器