runtime 3 ms, beats 98.44% of cpp submissions
O(m+n) solution with explanation

tags: string, stack

Simplify Path

📖 description

給定一個電腦內顯示檔案路徑的字串，要求簡化字串的表示 (去除多餘部分但表達不變)
要注意多重的 / 只表示成一個 / ，比如 ///// 相等於 /
而 . 表示當前層 ， .. 表示上一層
但是 … 則需要被視為是檔案名稱 (或資料夾名稱)
此外，結尾不需要多 / ，比如是 /stolas 而非 /stolas/

ex 1.
    Input: path = "/home/"

    Output: "/home"

    Explanation: 
        Note that there is no trailing slash 
        after the last directory name.

ex 2.

    Input: path = "/../"

    Output: "/"

    Explanation: 
        Going one level up from the root directory is a no-op, 
        as the root level is the highest level you can go.

ex 3.

    Input: path = "/home//foo/"

    Output: "/home/foo"

    Explanation: 
        In the canonical path, multiple consecutive slashes 
        are replaced by a single one.

🧠 solution

整體來說，我們需要處理資料是遇到 / 的時候，所以可以擷取出在兩個 / 內的資料來做判斷 (維護一個字串)，並創建一個儲存當前檔案路徑的陣列 (stack of string)。

當遇到 / 共有兩個狀況

  • 是正常檔案名稱，加入到結果中
  • 是 .. ，將最近一次加入的字串 pop 出來 (表示到上一層)

⏳ time complexity

遍歷一次輸入字串 O(n) ，遍歷一次結果陣列 O(m) ，其中 m 為輸入的檔案個數
總時間複雜度 O(m+n)

📝 code

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
33
class Solution {
public:
    string simplifyPath(string& path) {
        vector<string> st;
        string now = "",ans = "/";
        path+='/';  // 滿足條件，尋找兩個 / 間的資料
        for(int i=0;i<path.size();i++){
            if(path[i] == '/'){    
                if(now == ".."){        // 跳回到上一層
                    if(st.size()>0){    // 避免 pop 空 stack
                        st.pop_back();
                    }
                }
                else{
                    if(now.size()>0 && now!="."){   // 如果有存到字串且不是 .
                        st.emplace_back(now);
                    }
                }
                now = "";
            }
            else{
                now+=path[i];
            }
        }
        for(int i=0;i<st.size();i++){   // 組合結果
            ans+=st[i];
            if(i!=st.size()-1){
                ans+='/';
            }
        }
        return ans;
    }
};