leetcode71.Simplify Path

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
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.

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

简化unix风格的绝对路径。
这里简单说一下unix风格的路径：

  • .表示当前文件夹，即不进行任何操作
  • ..表示返回上层文件夹，如果已经至根目录，则不进行任何操作
  • /表示路径的分割线，多个连续的/等价于/

这里我们需要将复杂的unix路径，例如/a/./b/../../c/简化成最简形式/c

思路和代码

从直观的角度思考，每当路径上我们遇到具有含义的操作符时，就对其当前的路径进行操作。我们可以首先将所有的内容从/中分离出来，然后分别处理。这里我们需要用到堆栈的数据结构。堆栈有很多种实现方式，java中的Stack类LinkedList类都可以实现其功能。我们将读到的路径入栈，根据操作符出栈，最后将栈中剩余的元素组织成String路径返回即可。
代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public String simplifyPath(String path) {
    Stack<String> s = new Stack<String>();
    String[] pathDetail = path.split("/");
    for(int i = 0 ; i < pathDetail.length ; i++){
        //弹出上级目录，如果有上级目录
        if(pathDetail[i].equals("..")){
            if(s.isEmpty()){
                continue;
            }
            s.pop();
        //不进行任何操作
        }else if(pathDetail[i].equals(".") || pathDetail[i].isEmpty()){
            continue;
        }else{
            s.push(pathDetail[i]);
        }
    }
    if(s.isEmpty()){
        return "/";
    }
    StringBuilder result = new StringBuilder();
    do{
        result.insert(0, s.pop());
        result.insert(0, "/");
    }while(!s.isEmpty());
    return result.toString();
}

也可以使用链表实现： 

1
2
3
4
5
6
7
8
9
10
11
public String simplifyPath3(String path) {
    Deque<String> stack = new LinkedList<>();
    Set<String> skip = new HashSet<>(Arrays.asList("..",".",""));
    for (String dir : path.split("/")) {
        if (dir.equals("..") && !stack.isEmpty()) stack.pop();
        else if (!skip.contains(dir)) stack.push(dir);
    }
    String res = "";
    for (String dir : stack) res = "/" + dir + res;
    return res.isEmpty() ? "/" : res;
}