題目：Given an absolute path for a file (Unix-style), simplify it. For example, path = “/home/”, => “/home” path = “/a/./b/../../c/”, => “/c” Corner Cases: ? Did you consider the case where path = “/../”? In this case, you should return “/”. ? Another corner case is the path might contain multiple slashes ‘/’ together, such as “/home//foo/”. In this case, you should ignore redundant slashes and return “/home/foo”.
下面解法代碼的思想及編寫參考了網址https://github.com/soulmachine/leetcode#leetcode題解題目
代碼如下：
/ 時間復雜度 O(n)，空間復雜度 O(n)class Solution {public: string simplifyPath(const string& path) { vector<string> dirs; // 當做棧 for (auto i = path.begin(); i != path.end(); ) { ++i; auto j = find(i, path.end(), '/'); auto dir = string(i, j); if (!dir.empty() && dir != '.') { // 當有連續 '///' 時，dir 為空 if (dir == '..') { if (!dirs.empty()) dirs.pop_back(); } else dirs.push_back(dir); i = j; } ostringstream out; if (dirs.empty()) out << "/"; else { for (auto dir : dirs) out << "/" << dir; } return out.str(); }};新聞熱點
疑難解答
