ac solution code


  • 0

    Solution1. Stack - time = O(n), space = O(n)

    Question is:
    1) Jump to higher folder if meet ".." (Pop stack)
    2) Skip .
    3) Remove "/" after folder
    then output simplified folder path.

    Solution is:
    1) Split path with "/"
    2) Push dir if not ".", ".."
    3) If meet "..", pop stack (Jump to higher folder)

    e.g.
    path = "/a/./b/../../c/", => "/c":
    1) /../../ means 2 higher folder , so it's root folder,
    2) Remove / at end
    So output "/c"

    public String simplifyPath(String path) {
    	    Deque<String> stack = new LinkedList<>();
    	    Set<String> skip = new HashSet<>(Arrays.asList("..", ".", ""));
    	    
    	    for (String dir : path.split("/")) {            // <-Split original path into dirs with "/"
    	        if (dir.equals("..") && !stack.isEmpty())   // Meet "..", jump to higher level dir
                    stack.pop();     
    	        else if (!skip.contains(dir)) 
                    stack.push(dir);                        // Push dir
    	    }
    	    String res = "";
    	    for (String dir : stack) res = "/" + dir + res;
    	    return res.isEmpty() ? "/" : res;
    	}
    

Log in to reply
 

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