LeetCode 71. Simplify Path [Medium] [C++] 解題筆記

這題給定一個 Unix-style 系統上的路徑，要求我們將此路徑轉換為絕對路徑 (i.e. 最簡路徑 => 可以表達此路徑的最短 string)

EX:

        "/a/./b/../../c/"

Ans: "/c"

想法:

    路徑相關的題目通常可以採用 Stack 來解決，這題也一樣，我們利用一個 vector 當作 Stack 來存放路徑。

首先根據 "/" 依序分割路徑字串，以前面的例子會得到 "a" , "." , "b" , ".." , "c" , ''"。 

 其中 "." 表示當前目錄，".." 表示上一層目錄，最尾端會分割出空字串 ""，因此遇到 "." 或是 "" 可以直接忽略，而遇到 ".." 則需要

把最近存進 stack 的目錄刪掉 (pop())，因為 ".." 代表回到上一層，其他的字串表示目錄名稱直接放進stack即可。

最後要輸出時記得再把 '/' 加回去。

Complexity: O(n) time, O(n) space

完整程式碼:

class Solution {
public:
    string simplifyPath(string path) {
        string res;
        string tmp;
        stringstream ss(path);
        vector<string> stack;
        while (getline(ss, tmp, '/')) {
            if (tmp == "." || tmp == "") {
                continue; 
            }
            if (tmp == ".." && !stack.empty()) {
                stack.pop_back();
            }
            if (tmp != "..") {
                stack.push_back(tmp);
            }
        }
        for (auto& s : stack) {
            res += "/" + s;
        }
        
        return res.empty()? "/" : res;
    }
};