71. Simplify Path

Medium

Description

給定 Unix 風格的絕對路徑字串 path，將其簡化為標準路徑 (canonical path)。規則：
"." 表示當前目錄
".." 表示上一層目錄
多個連續斜線視為單一斜線
結果以 / 開頭且末尾不含 /

Example:

Input: path = “/home//foo/../bar” Output: “/home/bar”

Intuition#

核心思路：用斜線分割路徑，堆疊處理目錄名稱——普通名稱 push，".." 則 pop，"." 和空字串跳過。

路徑簡化本質上是「進入目錄 = push，返回上層 = pop」
先 split 再逐一處理，最後 join 成結果

Approaches#

⭐1: Stack + Split#

概念: 用 / 分割路徑，遍歷每個部分，根據規則操作堆疊，最後以 / 連接堆疊內容
時間複雜度: O(n) - n 為路徑長度
空間複雜度: 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: 路徑解析問題用堆疊處理「進入/返回」操作
關鍵技巧: split("/") 會產生空字串（連續斜線或開頭斜線），需要在 when 中一併處理掉。最後別忘了加上開頭的 /