#421 Simplify Path

题目描述：

Given an absolute path for a file (Unix-style), simplify it.

Have you met this question in a real interview?  Yes Example

"/home/", => "/home"

"/a/./b/../../c/", => "/c"

Challenge 

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".

题目思路：

这题由于有“..”的存在，需要用stack来除去path中的冗余部分。用两个指针start和end，start指向‘/’后一个数，end指向start后一个'/'。那么用start和end就可以找出两个'/'中间的string了。如果这个string不是'.'（因为如果是'.'的话可以忽略，进行下一步）：如果stack不为空并且string是'..'，那么需要把stack的top给pop出来，因为'..'表示又返回上一层path了；除此之外，如果string不是'..'，那么就把这个string push进stack中。

Mycode（AC = 20ms）：

class Solution { public: /** * @param path the original path * @return the simplified path */ string simplifyPath(string& path) { // Write your code here stack<string> helper; // find the string between '/' and '/' // work on stack based on string int start = 0, end = 0; string str = ""; while (end < path.length()) { end = path.find("/", start); if (end == string::npos) { str = path.substr(start); } else { str = path.substr(start, end - start); } if (str.length() > 0 && str != ".") { if (!helper.empty() && str == "..") { helper.pop(); } else if (str != "..") { helper.push(str); } } start = end + 1; } if (helper.empty()) { return "/"; } // get the full path from stack string short_path = ""; while (!helper.empty()) { short_path = helper.top() + short_path; helper.pop(); short_path = "/" + short_path; } return short_path; } };