1 題目描述



這個題目的目標是在把一個很複雜的路徑簡化成為一個簡單的路徑，例如：

  • input: /a/./b/../../c/
  • output: /c

從上面的例子來說，/a/b 進去後，往上一層，再往上一層，回到/，最後進到 /c，但直接寫成 /c 不就好了嗎？太蠢了，請簡化他！這就是題目的用意。

2 解法

從題目的思路來看，你會發現當遇到 /.. 的時候，就需要往上一層，其實就是把目前 stack 的最上面的目錄 pop 出來，當遇到正常的目錄而不是/. 或是 /.. 就可以放入 stack 裡面。從下面的圖片來看，以 /.../a/../b/c/../d/./ 為例子，我們可以看到 stack 的變化。（注意 /... 是一個目錄，因為他不是 /. 或是 /..）

從下圖來看，只要是正常檔案名稱，就放入 stack 裡面

當遇到 .. 的時候，就 pop 出來，當遇到 . 的時候，就不做任何事情，繼續往下走。

最後，把 stack 裡面的元素，用 / 串接起來，就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for i in path.split("/"):
            # 如果是空的或是當前目錄，就不做任何事情 
            if i == "" or i == ".":
                continue
            # 如果是上一層目錄，就 pop 出來 
            if i == "..":
                # 但是如果 stack 是空的，就不做任何事情 
                if len(stack) == 0:
                    continue
                else:
                    stack.pop()
            # 不是特殊標誌，就是一般檔案名稱，放入 stack 裡面
            else:
                stack.append(i)

        # 可以用 join 實現 
        ans = ""
        while not len(stack) == 0:
            ans = "/" + stack.pop() + ans
        if len(ans) == 0:
            ans = "/"
        return ans 

# 著重在需要做處理的部分 (if, elif)
        for i in path.split("/"):
            if stack and i == "..":
                stack.pop()
            elif i not in ["", ".", ".."]:
                stack.append(i)

但是我們發現應該可以簡化一下，因為 continue 的部分應該省略，專注在需要執行動作的條件if上。

1
2
3
4
5
6
7
8
9
10
11
# continue 的部分應該省略，專注在需要執行動作的條件if上
for i in path.split("/"):
    if i == "" or i == ".":
        continue
    if i == "..":
        if len(stack) == 0:
            continue
        else:
            stack.pop()
    else:
        stack.append(i)

以及最後的部分，我們可以用 join 實現，而不是用 while loop 來實現。

1
2
3
4
5
6
7
8
9
10
11
# 可以用 join 實現 
        ans = ""
        while not len(stack) == 0:
            ans = "/" + stack.pop() + ans
        if len(ans) == 0:
            ans = "/"
        print(ans)


# 改成這樣
print("/" + "/".join(stack))

修改後的程式碼如下

1
2
3
4
5
6
7
8
9
10
class Solution:
    def simplifyPath2(self, path: str) -> str:
        stack = []
        for i in path.split("/"):
            if stack and i == "..":
                stack.pop()
            elif i not in ["", ".", ".."]:
                stack.append(i)
        
        return "/" + "/".join(stack)

時間複雜度O(n) for 循環遍歷整個 s 列表在 split 過後，時間複雜度為 O(n)。
空間複雜度O(n) 空間複雜度由字典 stack 存儲 n 個不同的檔案名稱，因此空間複雜度為 O(n)。

3 總結

總結來說，很開心這個題目也是30分鐘內就寫出解決辦法，但是對於程式碼的簡化，還是需要多加練習，這個題目的特性就是你發現要有需要回到上一層的需求，stack會是一個很好的選擇，因為 pop() 可以把上面的元素拿掉，這樣就可以達到目的。