0071-简化路径

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 10:41:39 2023-09-13 10:41:39 Updated    

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..）
表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。
对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/' 。
  • 最后一个目录名（如果存在） 不能 以 '/' 结尾。
  • 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

**输入：** path = "/home/"
**输出：** "/home"
**解释：** 注意，最后一个目录名后面没有斜杠。

示例 2：

**输入：** path = "/../"
**输出：** "/"
**解释：** 从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

**输入：** path = "/home//foo/"
**输出：** "/home/foo"
**解释：** 在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

**输入：** path = "/a/./b/../../c/"
**输出：** "/c"

提示：

  • 1 <= path.length <= 3000
  • path 由英文字母，数字，'.'，'/' 或 '_' 组成。
  • path 是一个有效的 Unix 风格绝对路径。

方法一：栈

思路与算法

我们首先将给定的字符串 $\textit{path}$ 根据 $\texttt{/}$ 分割成一个由若干字符串组成的列表，记为 $\textit{names}$。根据题目中规定的「规范路径的下述格式」，$\textit{names}$ 中包含的字符串只能为以下几种：

  • 空字符串。例如当出现多个连续的 $\texttt{/}$，就会分割出空字符串；

  • 一个点 $\texttt{.}$；

  • 两个点 $\texttt{..}$；

  • 只包含英文字母、数字或 $\texttt{_}$ 的目录名。

对于「空字符串」以及「一个点」，我们实际上无需对它们进行处理，因为「空字符串」没有任何含义，而「一个点」表示当前目录本身，我们无需切换目录。

对于「两个点」或者「目录名」，我们则可以用一个栈来维护路径中的每一个目录名。当我们遇到「两个点」时，需要将目录切换到上一级，因此只要栈不为空，我们就弹出栈顶的目录。当我们遇到「目录名」时，就把它放入栈。

这样一来，我们只需要遍历 $\textit{names}$ 中的每个字符串并进行上述操作即可。在所有的操作完成后，我们将从栈底到栈顶的字符串用 $\texttt{/}$ 进行连接，再在最前面加上 $\texttt{/}$ 表示根目录，就可以得到简化后的规范路径。

代码

[sol1-C++]
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
class Solution {
public:
    string simplifyPath(string path) {
        auto split = [](const string& s, char delim) -> vector<string> {
            vector<string> ans;
            string cur;
            for (char ch: s) {
                if (ch == delim) {
                    ans.push_back(move(cur));
                    cur.clear();
                }
                else {
                    cur += ch;
                }
            }
            ans.push_back(move(cur));
            return ans;
        };

        vector<string> names = split(path, '/');
        vector<string> stack;
        for (string& name: names) {
            if (name == "..") {
                if (!stack.empty()) {
                    stack.pop_back();
                }
            }
            else if (!name.empty() && name != ".") {
                stack.push_back(move(name));
            }
        }
        string ans;
        if (stack.empty()) {
            ans = "/";
        }
        else {
            for (string& name: stack) {
                ans += "/" + move(name);
            }
        }
        return ans;
    }
};
[sol1-Java]
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
class Solution {
    public String simplifyPath(String path) {
        String[] names = path.split("/");
        Deque<String> stack = new ArrayDeque<String>();
        for (String name : names) {
            if ("..".equals(name)) {
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }
            } else if (name.length() > 0 && !".".equals(name)) {
                stack.offerLast(name);
            }
        }
        StringBuffer ans = new StringBuffer();
        if (stack.isEmpty()) {
            ans.append('/');
        } else {
            while (!stack.isEmpty()) {
                ans.append('/');
                ans.append(stack.pollFirst());
            }
        }
        return ans.toString();
    }
}
[sol1-C#]
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
public class Solution {
    public string SimplifyPath(string path) {
        string[] names = path.Split("/");
        IList<string> stack = new List<string>();
        foreach (string name in names) {
            if ("..".Equals(name)) {
                if (stack.Count > 0) {
                    stack.RemoveAt(stack.Count - 1);
                }
            } else if (name.Length > 0 && !".".Equals(name)) {
                stack.Add(name);
            }
        }
        StringBuilder ans = new StringBuilder();
        if (stack.Count == 0) {
            ans.Append('/');
        } else {
            foreach (string name in stack) {
                ans.Append('/');
                ans.Append(name);
            }
        }
        return ans.ToString();
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def simplifyPath(self, path: str) -> str:
        names = path.split("/")
        stack = list()
        for name in names:
            if name == "..":
                if stack:
                    stack.pop()
            elif name and name != ".":
                stack.append(name)
        return "/" + "/".join(stack)
[sol1-C]
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
64
char ** split(const char * s, char delim, int * returnSize) {
    int n = strlen(s);
    char ** ans = (char **)malloc(sizeof(char *) * n);
    int pos = 0;
    int curr = 0;
    int len = 0;
    
    while (pos < n) {
        while (pos < n && s[pos] == delim) {
            ++pos;
        }
        curr = pos;
        while (pos < n && s[pos] != delim) {
            ++pos;
        }
        if (curr < n) {
            ans[len] = (char *)malloc(sizeof(char) * (pos - curr + 1)); 
            strncpy(ans[len], s + curr, pos - curr);
            ans[len][pos - curr] = '\0';
            ++len;
        }
    }
    *returnSize = len;
    return ans;
}

char * simplifyPath(char * path){
    int namesSize = 0;
    int n = strlen(path);
    char ** names = split(path, '/', &namesSize);
    char ** stack = (char **)malloc(sizeof(char *) * namesSize);
    int stackSize = 0;
    for (int i = 0; i < namesSize; ++i) {
        if (!strcmp(names[i], "..")) {
            if (stackSize > 0) {
                --stackSize;
            } 
        } else if (strcmp(names[i], ".")){
            stack[stackSize] = names[i];
            ++stackSize;
        } 
    }
    
    char * ans = (char *)malloc(sizeof(char) * (n + 1));
    int curr = 0;
    if (stackSize == 0) {
        ans[curr] = '/';
        ++curr;
    } else {
        for (int i = 0; i < stackSize; ++i) {
            ans[curr] = '/';
            ++curr;
            strcpy(ans + curr, stack[i]);
            curr += strlen(stack[i]);
        }
    }
    ans[curr] = '\0';
    for (int i = 0; i < namesSize; ++i) {
        free(names[i]);
    }
    free(names);
    free(stack);
    return ans;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
func simplifyPath(path string) string {
    stack := []string{}
    for _, name := range strings.Split(path, "/") {
        if name == ".." {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]
            }
        } else if name != "" && name != "." {
            stack = append(stack, name)
        }
    }
    return "/" + strings.Join(stack, "/")
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var simplifyPath = function(path) {
    const names = path.split("/");
    const stack = [];
    for (const name of names) {
        if (name === "..") {
            if (stack.length) {
                stack.pop();
            } 
        } else if (name.length && name !== ".") {
            stack.push(name);

        }
    }
    
    return "/" + stack.join("/");
};

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是字符串 $\textit{path}$ 的长度。

  • 空间复杂度：$O(n)$。我们需要 $O(n)$ 的空间存储 $\textit{names}$ 中的所有字符串。

 Comments
On this page
0071-简化路径