Leetcode(71) Simplify Path

发表于 | 分类于

Description

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

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

In a UNIX-style file system, a period (‘.’) refers to the current directory, so it can be ignored in a simplified path. Additionally, a double period (“..”) moves up a directory, so it cancels out whatever the last directory was. For more information, look here: https://en.wikipedia.org/wiki/Path_(computing)#Unix_style

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

解法

根据题意，可总结规律有：按’/‘号分隔路径，中间是”.”的情况直接略过，是”..”时删掉它上面挨着的一个路径，而下面的边界条件给的一些情况中可以得知，如果是空的话返回”/“，如果有多个”/“只保留一个。这道题坑在路径中可以出现’.’，意思是如果两个斜杠之间出现了大于2个点或者点与其他字符混合的情况，应该按照路径处理。

具体代码如下：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    public String simplifyPath(String path) {
        StringBuffer res = new StringBuffer();
        Stack<String> s = new Stack<>();
        StringBuffer tmp = new StringBuffer();
        for (int i = 0; i < path.length(); i++) {
            if (path.charAt(i) == '/') {
                continue;
            } else if (path.charAt(i) == '.') {
                if (i + 1 == path.length()) {
                    continue;
                }
                if (i + 1 < path.length() && path.charAt(i + 1) == '/') {
                    continue;
                }
                if (i + 2 == path.length() && path.charAt(i + 1) == '.') {
                    if (!s.empty()) {
                        s.pop();
                    }
                    i++;
                } else if (i + 2 < path.length() && path.charAt(i + 1) == '.' && path.charAt(i + 2) == '/') {
                    if (!s.empty()) {
                        s.pop();
                    }
                    i++;
                } else {
                    StringBuffer strangename = new StringBuffer();
                    while (path.charAt(i) != '/') {
                        strangename.append(path.charAt(i));
                        i++;
                        if (i >= path.length()) {
                            break;
                        }
                    }
                    s.push(strangename.toString());
                    strangename.delete(0, strangename.length());
                }
            } else {
                while (path.charAt(i) != '/') {
                    tmp.append(path.charAt(i));
                    i++;
                    if (i >= path.length()) {
                        break;
                    }
                }
                s.push(tmp.toString());
                tmp.delete(0, tmp.length());
            }
        }
        if (!s.empty()) {
            List<String> l = new ArrayList<>();
            while (!s.empty()) {
                String t = s.pop();
                l.add(t);
            }
            for (int i = l.size() - 1; i >= 0; i--) {
                res.append("/" + l.get(i));
            }
            return res.toString();
        }
        return "/";
    }
}