Last Updated on 2022-03-14 by Clay
題目
Given a stringpath, which is an absolute path (starting with a slash'/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path. In a Unix-style file system, a period'.'refers to the current directory, a double period'..'refers to the directory up a level, and any multiple consecutive slashes (i.e.'//') are treated as a single slash'/'. For this problem, any other format of periods such as'...'are treated as file/directory names. The canonical path should have the following format: - The path starts with a single slash'/'. - Any two directories are separated by a single slash'/'. - The path does not end with a trailing'/'. - The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period'.'or double period'..') Return the simplified canonical path.
Example 1:
Input: path = "/home/" Output: "/home" Explanation: Note that there is no trailing slash after the last directory name.
Example 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.
Example 3:
Input: path = "/home//foo/" Output: "/home/foo" Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
Constraints:
1 <= path.length <= 3000pathconsists of English letters, digits, period'.', slash'/'or'_'.pathis a valid absolute Unix path.
題目輸入一組為絕對路徑的字串 path。而在 Linux 系統中， . 代表著當前的目錄、.. 代表著上一層目錄、而無論重複多少次的斜線符號 / 皆只被視為一次。
我們要做的，就是要返回輸入路徑的規範路徑（canonical path）。詳細的解釋與定義可以參考 stackoverflow 上的討論。
解題思路
因為存在著 .. 需要返回上一層目錄結構的情況，所以這題我很直覺地選擇了使用 stack 結構來儲存暫存目錄名稱。
首先開始遍歷原始輸入路徑 path，使用 temp 變數儲存目錄名稱，並在碰到 / 或是超出 path 長度時取消儲存目錄名稱。
接著就是判斷 temp 儲存的目錄名稱為何了。如果是正常的目錄名稱，則將其存放進 stack；如果是 . 則清空 temp 繼續查找下個目錄名稱；如果是 .. 則把 stack 內儲存的上一個目錄名稱彈出（如果 stack 結構非空的狀況）。
複雜度
因為遍歷了原始路徑的字串，以及儲存了大部分的目錄名稱，故時間複雜度與空間複雜度皆為 O(n)。
| Time complexity | O(n) |
| Space complexity | O(n) |
C++ 範例程式碼
class Solution {
public:
string simplifyPath(string path) {
// Init
string newPath;
stack<string> st;
// Check the raw path
for (int i=0; i<path.size(); ++i) {
string temp = "";
while (i<path.size() && path[i]!='/') {
temp.push_back(path[i]);
++i;
}
if (temp == "..") {
if (!st.empty()) st.pop();
}
else if (!temp.empty() && temp != ".") {
st.push(temp);
}
}
// Recombination
while (!st.empty()) {
newPath = '/' + st.top() + newPath;
st.pop();
}
if (newPath.empty()) return "/";
else return newPath;
}
};Python 範例程式碼
class Solution:
def simplifyPath(self, path: str) -> str:
# Init
new_path = ""
st = []
# Check the raw path
i = 0
while (i < len(path)):
temp = ""
while (i<len(path) and path[i]!="/"):
temp += path[i]
i += 1
if temp == "..":
if st: st.pop()
elif (temp and temp != "."):
st.append(temp)
# Step
i += 1
# Recombination
while st:
new_path = '/' + st.pop() + new_path
if not new_path: return "/"
else: return new_path