71 Simplify Path

题目链接：https://leetcode.com/problems/simplify-path/

题目：

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

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
click to show corner cases.

Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".

解题思路：

1. 以“/”为分隔符拆分字符串
2. 从后往前遍历拆分后的字符串数组，遇到“.”“..”“”的字符串，都赋值为null，同时还要记录“..”出现的次数num；遇到其它字符，则判断num是否大于0，若num大于0，则将当前出现的字符串也赋值为空，并num（即当前目录后有“..”，则回到当前目录的父目录，当前目录也就被抹去了）。
3. 此时字符串数组中的非空字符串，就是正确的目录了。遍历它们，用“/”将它们隔开。

注意：
特别强调区别
字符串引用为空 String s = null 与
空字符串s.equals(""); 的区别！！
若输入为“/”，用“/”拆分后得到的字符串数组不为null，而是两个长度为0的字符串！！！

StringBuffer sb = new StringBuffer();

上面这行代码创建了一个长度为0的字符串。

public class Solution {
    public String simplifyPath(String path) {
        String[] dirs = path.split("/");
        int len = dirs.length;
        int num = 0;
        for(int i = len - 1; i > 0; i --) {
            if(dirs[i].equals(".") || dirs[i].equals("")) {
                dirs[i] = null;
                continue;
            }
            if(dirs[i].equals("..")) {
                dirs[i] = null;
                num ++;
                continue;
            }
            if(num > 0) {
                dirs[i] = null;
                num --;
            }
        }
        StringBuffer sb = new StringBuffer();
        for(String d : dirs) {
            if(d == null || d.equals(""))
                continue;
            sb.append("/");
            sb.append(d);
        }
        if(sb.toString().equals(""))
            return "/";
        else
            return sb.toString();
    }
}

252 / 252 test cases passed.
Status: Accepted
Runtime: 360 ms

第二种解题思路：
参考链接：http://blog.csdn.net/linhuanmars/article/details/23972563

这道题目是Linux内核中比较常见的一个操作，就是对一个输入的文件路径进行简化。思路比较明确，就是维护一个栈，对于每一个块（以‘/’作为分界）进行分析，如果遇到‘../’则表示要上一层，那么就是进行出栈操作，如果遇到‘./’则是停留当前，直接跳过，其他文件路径则直接进栈即可。最后根据栈中的内容转换成路径即可（这里是把栈转成数组，然后依次添加）。时间上不会超过两次扫描（一次是进栈得到简化路径，一次是出栈获得最后结果），所以时间复杂度是O(n)，空间上是栈的大小，也是O(n)。

public class Solution {
    public String simplifyPath(String path) {  
        if(path == null || path.length()==0)  
        {  
            return "";  
        }  
        LinkedList<String> stack = new LinkedList<String>();  
        StringBuilder res = new StringBuilder();  
        int i=0;  

        while(i<path.length())  
        {  
            int index = i;  
            StringBuilder temp = new StringBuilder();  
            while(i<path.length() && path.charAt(i)!='/')  
            {  
                temp.append(path.charAt(i));  
                i++;  
            }  
            if(index!=i)  
            {  
                String str = temp.toString();  
                if(str.equals(".."))  
                {  
                    if(!stack.isEmpty())  
                        stack.pop();  
                }  
                else if(!str.equals("."))  
                {  
                    stack.push(str);  
                }  
            }  
            i++;  
        }  
        if(!stack.isEmpty())  
        {  
            String[] strs = stack.toArray(new String[stack.size()]);  
            for(int j=strs.length-1;j>=0;j--)  
            {  
              res.append("/"+strs[j]);  
            }  
        }  
        if(res.length()==0)  
            return "/";  
        return res.toString();  
    }  
}

252 / 252 test cases passed.
Status: Accepted
Runtime: 324 ms