| comments | difficulty | edit_url | tags | ||
|---|---|---|---|---|---|
true |
中等 |
|
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为 更加简洁的规范路径。
在 Unix 风格的文件系统中规则如下：
- 一个点
'.'表示当前目录本身。 - 此外，两个点
'..'表示将目录切换到上一级（指向父目录）。 - 任意多个连续的斜杠（即，
'//'或'///'）都被视为单个斜杠'/'。 - 任何其他格式的点（例如，
'...'或'....'）均被视为有效的文件/目录名称。
返回的 简化路径 必须遵循下述格式：
- 始终以斜杠
'/'开头。 - 两个目录名之间必须只有一个斜杠
'/'。 - 最后一个目录名（如果存在）不能 以
'/'结尾。 - 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含
'.'或'..'）。
返回简化后得到的 规范路径 。
示例 1：
输入：path = "/home/"
输出："/home"
解释：
应删除尾随斜杠。
示例 2：
输入：path = "/home//foo/"
输出："/home/foo"
解释：
多个连续的斜杠被单个斜杠替换。
示例 3：
输入：path = "/home/user/Documents/../Pictures"
输出："/home/user/Pictures"
解释：
两个点 ".." 表示上一级目录（父目录）。
示例 4：
输入：path = "/../"
输出："/"
解释：
不可能从根目录上升一级目录。
示例 5：
输入：path = "/.../a/../b/c/../d/./"
输出："/.../b/d"
解释：
"..." 在这个问题中是一个合法的目录名。
提示：
1 <= path.length <= 3000path由英文字母，数字，'.'，'/'或'_'组成。path是一个有效的 Unix 风格绝对路径。
我们先将路径按照 '/' 分割成若干个子串，然后遍历每个子串，根据子串的内容进行如下操作：
- 若子串为空，或者为
'.'，则不做任何操作，因为'.'表示当前目录； - 若子串为
'..'，则需要将栈顶元素弹出，因为'..'表示上一级目录； - 若子串为其他字符串，则将该子串入栈，因为该子串表示当前目录的子目录。
最后，我们将栈中的所有元素按照从栈底到栈顶的顺序拼接成字符串，即为简化后的规范路径。
时间复杂度
class Solution:
def simplifyPath(self, path: str) -> str:
stk = []
for s in path.split('/'):
if not s or s == '.':
continue
if s == '..':
if stk:
stk.pop()
else:
stk.append(s)
return '/' + '/'.join(stk)class Solution {
public String simplifyPath(String path) {
Deque<String> stk = new ArrayDeque<>();
for (String s : path.split("/")) {
if ("".equals(s) || ".".equals(s)) {
continue;
}
if ("..".equals(s)) {
stk.pollLast();
} else {
stk.offerLast(s);
}
}
return "/" + String.join("/", stk);
}
}class Solution {
public:
string simplifyPath(string path) {
deque<string> stk;
stringstream ss(path);
string t;
while (getline(ss, t, '/')) {
if (t == "" || t == ".") {
continue;
}
if (t == "..") {
if (!stk.empty()) {
stk.pop_back();
}
} else {
stk.push_back(t);
}
}
if (stk.empty()) {
return "/";
}
string ans;
for (auto& s : stk) {
ans += "/" + s;
}
return ans;
}
};func simplifyPath(path string) string {
var stk []string
for _, s := range strings.Split(path, "/") {
if s == "" || s == "." {
continue
}
if s == ".." {
if len(stk) > 0 {
stk = stk[0 : len(stk)-1]
}
} else {
stk = append(stk, s)
}
}
return "/" + strings.Join(stk, "/")
}function simplifyPath(path: string): string {
const stk: string[] = [];
for (const s of path.split('/')) {
if (s === '' || s === '.') {
continue;
}
if (s === '..') {
if (stk.length) {
stk.pop();
}
} else {
stk.push(s);
}
}
return '/' + stk.join('/');
}impl Solution {
#[allow(dead_code)]
pub fn simplify_path(path: String) -> String {
let mut s: Vec<&str> = Vec::new();
// Split the path
let p_vec = path.split("/").collect::<Vec<&str>>();
// Traverse the path vector
for p in p_vec {
match p {
// Do nothing for "" or "."
"" | "." => {
continue;
}
".." => {
if !s.is_empty() {
s.pop();
}
}
_ => s.push(p),
}
}
"/".to_string() + &s.join("/")
}
}public class Solution {
public string SimplifyPath(string path) {
var stk = new Stack<string>();
foreach (var s in path.Split('/')) {
if (s == "" || s == ".") {
continue;
}
if (s == "..") {
if (stk.Count > 0) {
stk.Pop();
}
} else {
stk.Push(s);
}
}
var sb = new StringBuilder();
while (stk.Count > 0) {
sb.Insert(0, "/" + stk.Pop());
}
return sb.Length == 0 ? "/" : sb.ToString();
}
}func simplifyPath(path string) string {
return filepath.Clean(path)
}