Java 10-lines solution with stack


  • 105
    S

    Hi guys!

    The main idea is to push to the stack every valid file name (not in {"",".",".."}), popping only if there's smth to pop and we met "..". I don't feel like the code below needs any additional comments.

    public String simplifyPath(String path) {
        Deque<String> stack = new LinkedList<>();
        Set<String> skip = new HashSet<>(Arrays.asList("..",".",""));
        for (String dir : path.split("/")) {
            if (dir.equals("..") && !stack.isEmpty()) stack.pop();
            else if (!skip.contains(dir)) stack.push(dir);
        }
        String res = "";
        for (String dir : stack) res = "/" + dir + res;
        return res.isEmpty() ? "/" : res;
    }
    

    Hope it helps!


  • 1
    L

    This code is very clear and easy to understand. I have a question: why do you use Deque instead of Stack? Is there some reason for using it here? Thanks.


  • 4
    L

    I guess the reason is that stack iterator will not iterate in order as you expected. See this: http://stackoverflow.com/questions/16992758/is-there-a-bug-in-java-util-stacks-iterator


  • 0
    L

    I see, thanks for the link. I think if we only use basic operators of stacks like pop, push, top, Stack in java works fine and need not to care about iterators.


  • 2
    S

    Hi! Actually, I always use Deque instead of Stack just because this is a good practice due to deprecation of Stack interface in Java. The reasons of deprecation (inheritance from Vector, etc.) are not related to the usage above but as Deque has just the same API than why not use it on permanent basis. :)


  • 6
    A

    Nice solution. One small comment, since you are using Deque, why not take advantage of [pool|peek]Last() methods in order to be able to use stringBuilder?

    StringBuilder sb = new StringBuilder();
            while (path.peekLast() != null) {
                sb.append('/');
                sb.append(path.pollLast());
            }

  • 25
    H

    Derived from shpolsky's code, using LinkedList and StringBuilder

    public class Solution {
    public String simplifyPath(String path) {
    	StringBuilder sb = new StringBuilder("/");
        LinkedList<String> stack = new LinkedList<String>();
    	for(String s: path.split("/")){
    		if(s.equals("..")){
    		    if(!stack.isEmpty())
    			    stack.removeLast();
    		}
    		else if(!s.equals("") && !s.equals("."))
    			stack.add(s);
    	}
    	for(String s: stack){
    		sb.append(s+"/");
    	}
    	if(!stack.isEmpty()) sb.setLength(sb.length()-1);
    	return sb.toString();
    }
    

    }


  • 1
    S

    Sorry, what is ------- if(!stack.isEmpty()) sb.setLength(sb.length()-1); ------this sentence used for? since I delete this one, the answer is wrong. Thank you so much.


  • 0
    D

    is it possible that multiple "/" together?


  • 0
    S

    This solution can not cover all the test cases like "abc/.../"


  • 0
    E

    I think that because each time we append s+"/" in builder and if stack is not empty, then finally an additional "/" will appear at the tail, so hyuna915 cuts it off.


  • 0
    H

    sb.append("/").append(stack.pollLast());


  • 0
    L

    Actually you can just use the stack. It iterates in the order you want since the underlying implementation is a list.

    Stack<String> stack = new Stack<>();
    
    for (String dir : stack){ 
        result.append("/");
        result.append(dir);
    }
    

  • 3

    I think my solution without using stack is also not bad. :) For your reference, https://discuss.leetcode.com/topic/57415/java-10-line-solution-without-stack

    ps: I think I forgot the cost of StringBuilder.insert() from head which is bad...

    Here is my Stack solution using String.join() to simplify last step.

        public String simplifyPath(String path) {
            Stack<String> s = new Stack<>();
            for (String p : path.split("/")) {
                if (p.isEmpty() || ".".equals(p)) continue;
                if ("..".equals(p)) {
                    if (!s.isEmpty()) s.pop();
                } else s.push(p);
            }
            return "/" + String.join("/", s);
        }
    

  • 0

    @cdai said in Java 10-lines solution with stack:

    return "/" + String.join("/", s);

    This is the highlight.


  • 0
    P

    @shpolsky

    
    second last line, why do you need + res at the end? 
    it looks like you are adding emty string at the end ? but in a loop res will change, so in second iteration you will not get empty string? please let me know if you need it for specific reason.
    
    for (String dir : stack) res = "/" + dir + res;
    

  • 0
    Y
    This post is deleted!

  • 0
    W

    Very nice solution! thx


  • 0
    Q

    @cdai that's interesting that you utilize the "bug iterator" of stack then get the right answer, well done


  • 0
    A

    @shpolsky - Really good solution. To concatenate the result from Deque.

            StringBuilder sb = new StringBuilder("");
            for(String s: stack){
                sb.insert(0,"/" + s);
    	 }
            return sb.toString().equals("") ? "/" : sb.toString();

Log in to reply
 

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