0%

LeetCode-Simplify Path

怎么说呢,其实这道题还挺简单的,但是边界情况有比较多,导致 Debug 了很久,真的是测试不规范,提交两行泪啊。

言归正传,思路就是使用一个 vector 来保存之前经历的路径,如果遇到需要忽略的合需要回退的就进行相应的操作,如果是其他种类的路径,就直接添加到 vector 之后。

然后就是有很多边界情况,比如 path 长度太小,最后回退到了根目录,给出的 path 最后不带“/”,所以导致解析错误等等。这些问题都需要先把测试用例写好再去调试代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
string simplifyPath(string path) {
if(path.size()<2) return "/";
path+='/';
vector<string*> canonical;
int i=0,j=1;
while(j<=path.size()){
if(path[j]!='/') j++;
else{
if((j-i==2 && path[i+1]=='.')||(j-i==1)){
;
}else if(j-i==3 && path[i+1]=='.' && path[i+2]=='.'){
if(canonical.size()!=0) canonical.pop_back();
}else{
canonical.push_back(new string(path.begin()+i+1,path.begin()+j));
}
i=j;
j++;
}
}
if(canonical.size()==0) return "/";
string ret="";
for(int i=0;i<canonical.size();i++){
ret+="/";
ret+=*(canonical[i]);
}
return ret;
}
};

看了一下 solutions C++ 10-lines solution,发现一个哥们太厉害了,把输入的 string 先转换成 stringstream,然后直接用 getline 当做 split 函数去做,代码就会简单很多(其实方法是一样的)

1
2
3
4
5
6
7
8
9
10
11
12
string simplifyPath(string path) {
string res, tmp;
vector<string> stk;
stringstream ss(path);
while(getline(ss,tmp,'/')) {
if (tmp == "" or tmp == ".") continue;
if (tmp == ".." and !stk.empty()) stk.pop_back();
else if (tmp != "..") stk.push_back(tmp);
}
for(auto str : stk) res += "/"+str;
return res.empty() ? "/" : res;
}