題目連結:
題目意譯:
給定一個字串 path,其為一個在 Unix 風格的檔案系統下指向一個檔案或目錄的絕對路徑(以一個斜線 '/' 作為開頭),將其轉變為一個簡化後的標準路徑。
在一個 Unix 風格的檔案系統中,一個句號 '.' 代表著當前目錄、一個雙重句號 '..' 代表著上一層的目錄,而多個連續的斜線(如 '//')則視為等同於單一斜線 '/'。對於本問題,任何其他格式之句號如 '...' 則將被視為檔案/目錄之名稱。
標準路徑應遵循以下格式:
路徑應以一個斜線 '/' 作為開頭。
任兩個目錄應以一個斜線 '/' 作為分隔。
路徑不應以一個末尾斜線 '/' 作為結尾。
路徑應只包含從根目錄到目標檔案或目錄之路徑上的目錄們(即,不應出現句號 '.' 或是雙重句號 '..')。
回傳簡化後的標準路徑。
限制:
1 ≦ path.length ≦ 3000
path 由英文字母、數字、句號 '.'、斜線 '/' 或 '_' 所組成。
path 是一個合法的絕對 Unix 路徑。
範例測資:
範例 1:
輸入: path = "/home/"
輸出: "/home"
解釋: 注意到在最後一個目錄名稱不應有末尾的斜線。
範例 2:
輸入: path = "/../"
輸出: "/"
解釋: 從根目錄往上一層為一個 no-op(無作用指令),因為根目錄為你可以抵達的最高層級。
範例 3:
輸入: path = "/home//foo/"
輸出: "/home/foo"
解釋: 在標準路徑中,多個連續斜線將被單一一個斜線所取代。
解題思維:
模擬即可,字串處理方式類似於
這題(不過該題的「上一層」是以「_」表示,本題的「_」單純是作為檔案名稱字元出現。剩下的細節不同處在此不贅述)。
也就是說我們利用一個堆疊來處理 path 這個字串(堆疊中每個元素為一個字串,每個字串為一個目錄或檔案)。處理過程中以斜線作為分界點,來分出各個目錄、檔案或是句號們。當遇到單一一個句號(即 '.')時,就忽略這個句號(因為其指涉當前目錄,等於沒有進展);當遇到雙重句號時,則移除堆疊頂端的字串,代表我們要回到上一層(除非堆疊為空,此時忽略此動作);剩下的就只會是普通的目錄或檔案名稱以及空字串(因為我們是以斜線作為分界,兩個連續斜線之間並無字元)而已,只要字串非空就丟到堆疊頂端。
最後把堆疊的元素從底部掃到頂端,每個元素之間用單一一個斜線互相連接在一起即是所求的標準路徑。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。