Wednesday, January 11, 2017

Leetcode/F家 微软 -- 71. Simplify Path(stack)

71. Simplify Path(Stack-Deque)
  • Difficulty: Medium
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

思路: split string by '/' into string [] , use a stack to store input.
           Notice "a//b" will be splited into "a", ''", "b". When ''(by"//") , "." just skip. 
           When ".." ,pop stack if not empty
Complexity: O(N)

关键字: Stack(use Deque is better), str.split(''/") into String[]

public class Solution {
    public String simplifyPath(String path) {
        Deque<String> deque = new LinkedList<String>();
        String[] splits = path.split("/");
        for (String split : splits) {
            if (split.equals("")||split.equals(".")){
                continue;
            }else if (split.equals("..")){
                if(!deque.isEmpty())deque.pop();
            }else{
                deque.push(split);
            }
        }
        StringBuilder builder = new StringBuilder();
        while (!deque.isEmpty()) {
            String s = deque.pop();
            builder.insert(0,s);
            builder.insert(0,"/");
        }
        if (builder.length() == 0)
            return "/";//edge case: "/../" return "/"
        return builder.toString();
        }
}

No comments:

Post a Comment