Friday, October 10, 2014

[Leetcode] 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".

vector<string> splitPath(string path)
    {
        vector<string> ret;
        int i=0;
        while(i < path.size())
        {
            while(i < path.size() && path[i] != '/')
                i++;
            int j = i;
            i++;
            while(i < path.size() && path[i] != '/')
                i++;
                
            if (j != path.size())
                ret.push_back(path.substr(j+1, i-(j+1)));
        }
        return ret;
    }

    string simplifyPath(string path) {
        vector<string> paths = splitPath(path);
        stack<string> s;
        for(int i=0; i<paths.size(); i++)
        {
            //case: "/.."
            if (paths[i] == "..")
            {
                if (!s.empty())
                    s.pop();
            }
            //case: "////"
            else if (paths[i] != "." && paths[i].size() > 0)
                s.push(paths[i]);
        }
        
        string outPath;
        while(!s.empty())
        {
            string p = s.top();
            s.pop();
            outPath.insert(0, p);
            outPath.insert(0,"/");
        }
        
        if (outPath.size() == 0)
            outPath = "/";
            
        return outPath;
        
    }

No comments:

Post a Comment