給定 Unix 風格的絕對路徑字串
path，將其簡化為標準路徑 (canonical path)。規則：
"."表示當前目錄".."表示上一層目錄- 多個連續斜線視為單一斜線
- 結果以
/開頭且末尾不含/
Example:
Input: path = “/home//foo/../bar” Output: “/home/bar”
Intuition
TIP
核心思路：用斜線分割路徑，堆疊處理目錄名稱——普通名稱 push，".." 則 pop，"." 和空字串跳過。
- 路徑簡化本質上是「進入目錄 = push，返回上層 = pop」
- 先 split 再逐一處理，最後 join 成結果
Approaches
1. Manual Scan (no split) — O(n) / O(n)
- Idea: 自己掃字元切出每段，省去
split產生的中間清單；遇.略過、..退一層、其餘入堆 - Time:
O(n) - Space:
O(n)- 堆疊
class Solution {
fun simplifyPath(path: String): String {
val stack = ArrayDeque<String>()
var i = 0
val n = path.length
while (i < n) {
while (i < n && path[i] == '/') i++ // 跳過連續斜線
val start = i
while (i < n && path[i] != '/') i++ // 取一段
if (i > start) {
when (val part = path.substring(start, i)) {
"." -> {}
".." -> if (stack.isNotEmpty()) stack.removeLast()
else -> stack.addLast(part)
}
}
}
return "/" + stack.joinToString("/")
}
}⭐ 2. Stack + Split — O(n) / O(n)
- Idea: 用
/分割路徑，遍歷每個部分，根據規則操作堆疊，最後以/連接堆疊內容 - Time:
O(n)- n 為路徑長度 - Space:
O(n)
class Solution {
fun simplifyPath(path: String): String {
val stack = ArrayDeque<String>()
for (part in path.split("/")) {
when (part) {
"", "." -> continue
".." -> {
if (stack.isNotEmpty()) stack.removeLast()
}
else -> stack.addLast(part)
}
}
return "/" + stack.joinToString("/")
}
}🔑 Takeaways
- Pattern: 路徑解析問題用堆疊處理「進入/返回」操作
- Key trick:
split("/")會產生空字串（連續斜線或開頭斜線），需要在 when 中一併處理掉。最後別忘了加上開頭的/