kiddy

Simplify Path

leave a comment »

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Solution:
Since the input can only be a valid absolute path for a file(Unix-style), the input are constrained strictly.
1) repeating ‘/’
2) elements between ‘/’s can only be “.”, “..”, or other file name.
so the main task is to eliminate the ‘/’ and find the elements.
“.” means current folder.
“..” means parent folder.
others mean the children folder.

class Solution {
public:
    string simplifyPath(string path) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int len = path.size();
        string result = "";
        assert(path[0] == '/');
        int ind = 0;      
        stack<string> ss;
        while(ind < len){
            while(ind < len && path[ind] == '/'){
                ind++;
            }
            if(ind == len)    break;
            int begin = ind;
            int end = ind;
            while(end<len && path[end] != '/'){
                end++;
            }
            string element = path.substr(begin, end-begin);
            ind = end;
            if(element == "."){
                continue;
            }else if(element == ".."){
                if(ss.size()>0){
                    ss.pop();
                }
            }else{
                ss.push(element);
            }            
        }
        if(ss.size() == 0)  return "/";
    	int size = ss.size();
        for(int i = 0; i < size; i++){
            result = "/" + ss.top() + result;
            ss.pop();
        }
        return result;
    }
};
Advertisements

Written by linzhongzl

April 29, 2013 at 4:38 pm

Posted in Leetcode

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: