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;
        
        
    }
};