LeetCode 71. 簡化路徑（棧）

1. 題目

以 Unix 風格給出一個檔案的絕對路徑，你需要簡化它。或者換句話說，将其轉換為規範路徑。

在 Unix 風格的檔案系統中，一個點（

）表示目前目錄本身；此外，兩個點（

..

）表示将目錄切換到上一級（指向父目錄）；兩者都可以是複雜相對路徑的組成部分。

請注意，傳回的規範路徑必須始終以斜杠

開頭，并且兩個目錄名之間必須隻有一個斜杠

。最後一個目錄名（如果存在）不能以 / 結尾。此外，規範路徑必須是表示絕對路徑的最短字元串。

示例 1：
輸入："/home/"
輸出："/home"
解釋：注意，最後一個目錄名後面沒有斜杠。

示例 2：
輸入："/../"
輸出："/"
解釋：從根目錄向上一級是不可行的，因為根是你可以到達的最進階。

示例 3：
輸入："/home//foo/"
輸出："/home/foo"
解釋：在規範路徑中，多個連續斜杠需要用一個斜杠替換。

示例 4：
輸入："/a/./b/../../c/"
輸出："/c"

示例 5：
輸入："/a/../../b/../c//.//"
輸出："/c"

示例 6：
輸入："/a//b////c/d//././/.."
輸出："/a/b/c"

複制

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/simplify-path

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 棧解題

需要考慮四種情況 / , . , .. , 其他
用棧來記錄路徑，遇到 .. 彈棧，遇到 其他 壓棧

class Solution {
public:
    string simplifyPath(string path) {
        stack<string> stk;
        string file;
        path += '/';	//便于處理最後一次邊界
        for(int i = 0; i < path.size(); ++i)
        {
            if(path[i] == '/')	//遇到分隔符，需要處理
            {
                if(file == "..")
                {
                    if(!stk.empty())
                        stk.pop();
                }
                else if(file != "" && file != ".")
                    stk.push(file);
                file = "";	//處理完，清空
            }
            else// ！= '/'
            {
                file += path[i];
            }
        }

        string ans;
        while(!stk.empty())
        {
            ans = '/'+stk.top()+ans;
            stk.pop();
        }
        if(ans == "")
            return "/";
        return ans;
    }
};

複制