Vue.js

Appearance

On this page

实战：简化路径 ​

Unix 风格的路径有一些特殊规则：

  • . 表示当前目录
  • .. 表示上一级目录
  • 多个连续斜杠 // 等同于单个斜杠 /

给你一个路径 /a/./b/../../c/，你能简化成什么？

答案是 /c。这个过程就像你在文件系统中导航：进入 a，停在当前位置，进入 b，退回上级，再退回上级，进入 c。

问题描述 ​

LeetCode 71. Simplify Path

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

规则：

  • 单个句点 . 表示当前目录
  • 双句点 .. 表示上一级目录
  • 多个连续斜杠视为单个斜杠
  • 任何其他格式的点（如 ...）视为普通目录名

返回的规范路径必须遵循：

  • 始终以斜杠 / 开头
  • 两个目录名之间只有一个斜杠
  • 不以斜杠结尾（根目录 / 除外）

示例：

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

输入：path = "/../"
输出："/"（不能再往上了，留在根目录）

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

问题分析 ​

首先想一下：为什么要用栈？

因为 .. 的语义是"返回上级"，这正好对应栈的"弹出"操作：

  • 普通目录名 → 入栈
  • .. → 出栈（如果栈不为空）
  • . → 什么都不做

所以这道题的思路是：用 / 分割路径，然后用栈模拟目录导航。

解法：栈 + 字符串分割 ​

javascript
function simplifyPath(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('/');
}

执行过程可视化 ​

以 path = "/a/./b/../../c/" 为例：

split('/') 结果：
['', 'a', '.', 'b', '..', '..', 'c', '']

遍历：

'': 空字符串，忽略

'a': 普通目录，入栈
     stack = ['a']

'.': 当前目录，忽略

'b': 普通目录，入栈
     stack = ['a', 'b']

'..': 返回上级，出栈
      stack = ['a']

'..': 返回上级，出栈
      stack = []

'c': 普通目录，入栈
     stack = ['c']

'': 空字符串，忽略

结果：'/' + 'c' = '/c'

为什么 split 会产生空字符串？ ​

javascript
'/a/b/'.split('/')
// 结果：['', 'a', 'b', '']
  • 开头的 / 前面没有内容 → 空字符串
  • 结尾的 / 后面没有内容 → 空字符串
  • 连续的 // 中间没有内容 → 空字符串

我们的代码统一处理这些情况：空字符串直接忽略。

边界情况 ​

1. 根目录的 .. ​

输入：/../
split 结果：['', '..', '']

遍历：
'..': 栈为空，忽略（不能再往上了）

结果：'/' + '' = '/'

2. 连续斜杠 ​

输入：/home//foo
split 结果：['', 'home', '', 'foo']

遍历：
'home': 入栈
'': 忽略
'foo': 入栈

结果：'/home/foo'

3. ... 是合法目录名！ ​

输入：/.../a
split 结果：['', '...', 'a']

遍历：
'...': 不是 '.' 也不是 '..'，是普通目录名，入栈
'a': 入栈

结果：'/.../a'

常见错误 ​

错误1：把 ... 当作特殊字符

javascript
// ❌ 错误：把 '...' 当作 '..' 处理
if (part.startsWith('..')) {
  stack.pop();
}

// ✅ 正确：只有恰好是 '..' 才特殊处理
if (part === '..') {
  stack.pop();
}

错误2：根目录继续 ..

javascript
// ❌ 错误：无条件出栈
stack.pop();  // 栈为空时会报错或返回 undefined

// ✅ 正确：检查栈是否为空
if (stack.length > 0) {
  stack.pop();
}

错误3：忘记开头的斜杠

javascript
// ❌ 错误：直接 join
return stack.join('/');  // 结果是 'a/b' 而不是 '/a/b'

// ✅ 正确：开头加 /
return '/' + stack.join('/');

复杂度分析 ​

  • 时间复杂度：O(n)，遍历路径中的每个字符
  • 空间复杂度：O(n)，栈和分割后的数组

简洁写法 ​

用 filter 和 reduce 可以写得更简洁：

javascript
function simplifyPath(path) {
  const stack = path.split('/').reduce((stack, part) => {
    if (part === '..') {
      stack.pop();
    } else if (part && part !== '.') {
      stack.push(part);
    }
    return stack;
  }, []);
  
  return '/' + stack.join('/');
}

技巧总结 ​

简化路径的核心：

  • 栈模拟目录：入栈 = 进入目录，出栈 = 返回上级
  • split 分割：用 / 分割得到各个部分
  • 三种情况：
    • 空或 . → 忽略
    • .. → 出栈
    • 其他 → 入栈
  • 根目录边界：栈为空时 .. 无效

这道题是栈应用的又一经典例题。它模拟了真实的文件系统导航过程。

关联题目 ​

  • LeetCode 394：字符串解码（栈处理嵌套）
  • LeetCode 150：逆波兰表达式求值
  • LeetCode 1190：反转每对括号间的子串

在 GitHub 上编辑此页