71. Simplify Path (Medium) Facebook Microsoft

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

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

Solution 1: Stack + String O(n^2); O(n^2)

    public String simplifyPath(String path) {
        if (path == null) {
            return "";
        }

        Stack<String> stack = new Stack<>();
        for (String s : path.split("/")) {
            if (s.equals("..")) {
                if (!stack.empty()) {
                    stack.pop();
                }
            } else if (!s.equals("") && !s.equals(".")) {
                stack.push(s);
            }
        }

/*        String res = "";
        while (!stack.empty()) {
            res = "/" + stack.pop() + res;
        }
        return res.length() == 0 ? "/" : res;*/
        return "/" + String.join("/", stack);
    }

Solution 2: ArrayList + StringBuilder O(n); O(n)

    /**
     * ArrayList + StringBuilder O(n);O(n)
     * insert和delete操作都要在尾端进行，但是如果要用StringBuilder，则最后连接时要从头开始遍历数据结构，所以不能用Stack.
     * 可以用ArrayList, 甚至LinkedList，但LinkedList效率低些，因为delete操作要遍历整个链表。
     * 当然也可以用Deque，但是没有必要。
     * Use ArrayList to store the temporary result.
     * Split the path with slash.
     * For each string s:
     *   If s equals two points, then if list is not empty, remove last one in list.
     *   Otherwise, if s is not empty or does not equal one point, add s to list.
     * Use StringBuilder to generate the result string.
     */
    public String simplifyPathB(String path) {
        if (path == null || path.length() == 0) {
            return "";
        }

        List<String> list = new ArrayList<>(); //List<String> list = new LinkedList<>();
        for (String s : path.split("/")) { // "/home/" -> "", home
            System.out.println(s);
            if (s.equals("..")) {
                if (!list.isEmpty()) {
                    list.remove(list.size() - 1);
                }
            } else if (!s.equals("") && !s.equals(".")) {
                list.add(s);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (String s : list) {
            sb.append("/" + s);
        }
        return sb.length() == 0 ? "/" : sb.toString();
    }