题目：

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

For example,

path = "/home/", => "/home"

path = "/a/./b/../../c/", => "/c"

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".

链接： 

题解：

简化路径，可以使用栈，deque以及LinkedList。遇到".."时，假如list不为空，移除末尾元素。假如当前string不为""或者"."，加入到list中。最后判断特殊情况"/"。

Time Complexity - O(n)， Space Complexity - O(n)。

public class Solution {    public String simplifyPath(String path) {        if(path == null || path.length() == 0)            return path;        LinkedList
     
       list = new LinkedList<>();                for(String s : path.split("/")) {            if(s.equals("..")) {                if(!list.isEmpty())                    list.removeLast();            } else if (!(s.equals("") || s.equals("."))) {                list.add(s);            }        }                StringBuilder sb = new StringBuilder("/");                for(String s : list) {            sb.append(s);            sb.append("/");        }                if(!list.isEmpty())                 //special case "/"            sb.setLength(sb.length() - 1);                return sb.toString();        }}
     

 

二刷：

以前的记录都写得不太仔细。二刷的时候要好好补充。

没用过Unix，这里读完题目我们首先要分析一些可能情况。

1. "/"是根目录
2. 遇到".."的话，这算是一个特殊操作符，我们要返回上一级目录
3. 遇到"."的或者""的话，我们不做改变
4. 否则，这段string可以被用作relative path

这里我们先初始化一个LinkedList<String>  list用来保存结果，把原来的path根据"/" split成一小段一小段，然后根据上面的逻辑对每一小段进行判断，符合条件的加入到list中，或者遇到".."从list中removeLast()。处理完毕之后遍历list中的所有小段。这里我们先建立一个"/"打头的StringBuilder，接下来每次append list中的string时，我们都append一个"/"。最后判断list是否为空，假如不为空，根据题意，我们需要去除掉最后加入的"/"。 （比如/home/ ， 我们需要return  /home）。 

Java:

Time Complexity - O(n)， Space Complexity - O(n)。

public class Solution {    public String simplifyPath(String path) {        if (path == null || path.length() == 0) {            return "/";        }        String[] relativePaths = path.split("/");        LinkedList
     
       list = new LinkedList<>();        for (String s : relativePaths) {            if (s.equals("..")) {                if (!list.isEmpty()) {                    list.removeLast();                        }            } else if (!(s.equals("") || s.equals("."))){                list.add(s);            }        }        StringBuilder sb = new StringBuilder("/");        for (String s : list) {            sb.append(s);            sb.append("/");        }        if (!list.isEmpty()) {            sb.setLength(sb.length() - 1);        }        return sb.toString();    }}
     

 

三刷:

先Split整个path by "/"， 然后建立一个stack / deque或者doubly linked list。 遍历split好的数组， 当数组当前元素p不为 ""， "."和".."的时候，我们push p 入栈， 否则当p为".."并且栈非空的情况下，我们pop上一个元素出栈。

最后用一个StringBuilder来输出结果。  这里选择了stack所以每次StringBuilder还要insert(0, stack.pop())，使用doubly linekd list或者deque的话就可以从队首遍历了，能节约不少时间。

 

public class Solution {    public String simplifyPath(String path) {        if (path == null || path.length() < 2) return path;        Stack
     
       stack = new Stack<>();                for (String p : path.split("/")) {            if (!p.equals(".") && !p.equals("..") && !p.equals("")) stack.push(p);            else if (p.equals("..") && !stack.isEmpty()) stack.pop();         }                StringBuilder res = new StringBuilder();        while (!stack.isEmpty()) res.insert(0, stack.pop()).insert(0, "/");        return res.length() == 0 ? "/" : res.toString();    }}