### leetcode Question 98: Simplify Path

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

### Updated(201309):

#### Analysis:

(1) Use a stack to store the path.
(2) Use a int flag to store the '/' pair
(3) First remove the "//" in the path.
(4) meets ".", do nothing, meets ".." pop stack if not empty, other strings push into stack.

#### Code:

class Solution {
public:
string simplifyPath(string path) {
// Start typing your C/C++ solution below
// DO NOT write int main() function

//Remove double "//"
int i=0;
while (i<path.size()-1){
if (path[i]=='/' && path[i+1]=='/'){
path.erase(i,1);
}else{ i++; }
}
//Add a '/' in the end.
if (path[path.size()-1]!='/'){path=path+"/";}

//main part
stack<string> dirs;
string str="";
int flag =0;
for (int i=0;i<path.size();i++){
if (path[i]=='/'){flag++;}
if (flag==1){ str+=path[i];}
if (flag==2){
if (str=="/.." && !dirs.empty()){
dirs.pop();
}
if (str!="/." && str!="/.."){
dirs.push(str);
}
flag=1;
str="/";
}
}

//Output Result
if (dirs.empty()){return "/";}
str="";
while (!dirs.empty()){
str=dirs.top()+str;
dirs.pop();
}
return str;
}
};


Analysis(old version):
The criterion is when meet "..", go to previous folder, meet ".", current folder, otherwise, go into next folder.

For implementation:

(1) function strtok(char*, const char*), note that  " string.c_str() " returns "const char*" but not "char*", one way is to create a new char* with the same length (by  char*  =  new char [length+1] ), and then use function "strcpy(target_char*, source_char*)".

(2) In the loop of getting strtok()  " pth = strtok(NULL, "/") " NULL mean continues scanning previous call.

(3) Use "strcmp" to compare char* ,  where returns 0 if equals.

(4) Be careful with the output order of stack.

Code(old version):
class Solution {
public:
string simplifyPath(string path) {
// Start typing your C/C++ solution below
// DO NOT write int main() function

stack<char*> st; //store folders

//get token
char* pth = new char [path.size()+1];
strcpy(pth,path.c_str());
char* tok = strtok(pth,"/");

while (tok!=NULL){

if (strcmp(tok,".")!=0){st.push(tok);}  //if meet "." do nothing.
if ((!st.empty())&&(strcmp(st.top(),"..")==0)){
//if meet "..", pop ".." and pop one more if available
st.pop();
if (!st.empty()){st.pop();}
}
tok = strtok(NULL,"/");
}

string res; //get result (be careful with the order of stack)
while (!st.empty()){
res = "/" + string(st.top())+ res;
st.pop();
}

if (res.empty()) return "/";
return res;

}
};


#### 1 comment:

1. like your solution, but would "erase" operation cost too much? Add a line [ if (i < path.size() - 1 && path[i] == path[i + 1])continue; ] will do the job