C++ 10-lines solution


  • 136
    M

    C++ also have getline which acts like Java's split. I guess the code can comment itself.

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

  • 0
    W

    Brilliant concise!


  • 9
    R

    you do not need to check for .. two times, you need to put checking for empty inside the if

    class Solution {
    public:
        string simplifyPath(string path) {
            string result="", token;
            stringstream ss(path);
            vector<string> tokens;
            while(getline(ss, token, '/')){
                if(token=="." || token=="") continue;
                else if(token==".."){
                    if(tokens.size()!=0)  tokens.pop_back();
                }
                else tokens.push_back(token);
            }
            if(tokens.size()==0) return "/";
            for(int i=0; i<tokens.size(); ++i)
                result=result+'/'+tokens[i];
            return result;
        }
    };

  • 0
    R
    class Solution(object):
        def simplifyPath(self, path):
            split = path.split('/')
            ans=[]
            for e in split:
                if e=='.' or e=='':
                    pass
                elif e == '..':
                    if len(ans)>0:
                        ans.pop()
                else:
                    ans.append(e)
            ttans = ''
            for e in ans:
                ttans += '/' + e
            return ttans if len(ttans)>0 else '/'
    

    elegant python code : )

    but could anybody tell me, why '/.' means '/', I am not clear about some requirments


  • 0
    C

    Because '.' means 'right here in the current directory'. It means no change.


  • 0
    R

    cool, and also ////// means /, but why /../../.. is also valid input, I think it is invalid


  • 1

    A concise Java version:

    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<String>();
       
        for(String token : path.split("/")) {
            if(token.equals("..")) {
               if(!stack.isEmpty()) stack.pop();
           
            } else if(!token.isEmpty() && !token.equals(".")) {
                stack.push(token);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append("/").append(stack.pollLast());   
        }
        
        return sb.length() == 0 ? "/" : sb.toString();
    }

  • 0
    A

    Awesome solution


  • 0
    U

    I guess it means that:
    1. you are in the root directory (first '/', cwd = root)
    2. you are trying to return to parental directory (the subsequent '../'), while root's parental directory is still itself.
    You can try this in a linux terminal, for example:
    1. cd / ;
    2. cd .. ;


  • 1
    S

    According to your answer "." --> "/" "./../.." -- > "/"
    I think the correct answer should be "." --> "." "./../.." --> "./../../" "/." --> "/" "/./../../" --> "/" So the answer should consider if path is start from root.


  • 0
    Y

    return '/'+'/'.join(ans)


  • 0
    H

    How do you know:
    for(auto str : stk) will ensure the elements in order? Could you give me a reference for that? I could not find it. Thanks


  • 0
    K

    Excellent ! Using getline operation and stringstream to implement split method is awesome!


  • 1
    A

    @monaziyi I am sure if given this problem, the interviewer's intention would be char manipulation with bare hands, not calling all kinds of library function. Otherwise there is no point of giving such a problem like this in interview, which is literally not an algorithm problem at all.


  • 0
    X

    @ayuanx I do not agree with you. I think the point of this problem is testing the usage of stack not how to split a string.


  • 0
    L

    @snail_go Agreed.
    ./ == > ./
    ./../.. ==> ./../../

    Seems OJ doesn't handle these cases correctly.


  • 0
    C

    My solution is very similar but I use deque instead of vector. Performance is not my initial concern when I choose deque over vector but I do see a small performance advantage of using deque. Maybe vector will relocate more often than deque when its size changes.


  • 0
    X

    Just change

    if (tmp == ".." and !stk.empty()) stk.pop_back();
    else if (tmp != "..") stk.push_back(tmp);
    

    to

    if (tmp != "..") stk.push_back(tmp);
    else if (!stk.empty()) stk.pop_back();
    

    then we don't need to check for .. two times.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.