71. Simplify Path

Leetcode link

题目简介

/**
 * @param {string} path
 * @return {string}
 */

题目给我们 一个字符串 path 代表某个 Unix 风格文件绝对路径，其特点为：

• '.' 代表当前目录
• '..' 代表上级目录
• 连续的多个 '///' 代表一个 '/'
• '...', '....' 这种超过两个的点，要当成文件名对待

题目要求我们将其简化为：

• 路径开头必须有一个 '/'
• 路径中只能有一个 '/' 区分不同文件夹
• 路径最后不能有 '/'
• 路径不能有 '.' 或 '..'，需要用文件本身表示

最后返回新的路径字符串

解题思路

这题我们需要用到栈来帮助处理 .. 的情况

具体而言，我们维护一个栈 stack，然后遍历由 path.split('/') 构成的数组 arr

• 如果遇到 . 或 ''，我们可以直接忽略

• 如果遇到 ..，我们需要把 stack 的栈顶元素出栈

• 其他情况我们可以直接 push 进栈

最后我们把 stack 根据 / 还原回字符串，然后给开头加上 / 即可返回

Javascript

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
    const arr = path.split('/')
    const stack  = []

    for(const item of arr) {
        switch(item) {
            case '.':
            case '':
                break;
            case '..': 
                stack.pop()
                break;
            default:
                stack.push(item)
        }
    }
    const res = stack.join('/')
    return '/' + res
};

复杂度分析

时间

O(n)

空间

O(n)