Simplify Path：LeetCode

Simplify Path：LeetCode2015-09-28原题链接: http://oj.leetcode.com/problems/simplify-path/

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

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（）;}

这道题其实还有一种做法，不需要维护栈，也就是不用额外空间，但是要对字符位置进行比较好的记录或者回溯，可能会多扫描一次，但是不会增加时间复杂度的量级。不过那个方法虽然对于空间上有提高，但是有很多细节的操作，并且没有什么算法思想，属于纯字符串操作，个人觉得意义不是很大，而且在面试中也很难正确写出来，还是比较推荐上述解法。

作者：csdn博客 Code_Ganker