Simplify Path:
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".
如果想按字符遍历的话就比较烦了，所以不如按'/' 斜杠来分割，然后按词来处理，就变成一个简单的栈的处理了。
class Solution {
public:
string simplifyPath(string path) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<string> st;
string label;
int start=0;
while(getLabel(path,start,label))
{
if ( label.compare("/") ==0 )
{
if ( st.empty() || st.back().compare("/")!=0)
st.push_back(label);
}
else if ( label.compare("..")==0)
{
assert(!st.empty()&&st.back().compare("/")==0);
st.pop_back();
if (!st.empty())
st.pop_back();
}
else if ( label.compare(".")==0)
{
assert(!st.empty()&&st.back().compare("/")==0);
st.pop_back();
}
else
{
assert(!st.empty()&&st.back().compare("/")==0);
st.push_back(label);
}
}
string ret;
vector<string>::iterator it;
for(it=st.begin();it!=st.end();++it)
ret.append(*it);
if (ret.length()>0 && ret.back()=='/')
ret.pop_back();
if ( ret.empty() )
ret.append("/");
return ret;
}
bool getLabel(string& path,int& start, string& label)
{
int len=path.length();
if ( start==len)
return false;
if ( path[start]=='/')
{
label="/";
start++;
return true;
}
int end =start+1;
while( end<len)
{
if(path[end]=='/')
break;
end++;
}
label=path.substr(start,end-start);
start=end;
return true;
}
};
之前还自己写个分割的函数，太Naive了，直接用库函数find就好了呀：
class Solution {
public:
string simplifyPath(string path) {
// Note: The Solution object is instantiated only once and is reused by each test case.
vector<string> st;
string::iterator it=path.begin();
string::iterator pre=it;
while((it=find(it,path.end(),'/'))!=path.end())
{
string tmp(pre,it);
if(tmp.empty()||tmp==".")
{
}
else if (tmp=="..")
{
if(!st.empty())
st.pop_back();
}
else
st.push_back(tmp);
pre=++it;
}
string ans;
for(int i=0;i<st.size();i++)
{
ans.push_back('/');
ans.append(st[i]);
}
if(ans.empty())
return "/";
else
return ans;
}
};