| comments | difficulty | edit_url | tags | ||
|---|---|---|---|---|---|
true |
中等 |
|
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
- 始终以斜杠
'/'开头。 - 两个目录名之间必须只有一个斜杠
'/'。 - 最后一个目录名（如果存在）不能 以
'/'结尾。 - 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含
'.'或'..'）。
返回简化后得到的 规范路径 。
示例 1：
输入：path = "/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入：path = "/../" 输出："/" 解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。
示例 3：
输入：path = "/home//foo/" 输出："/home/foo" 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入：path = "/a/./b/../../c/" 输出："/c"
提示：
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)
}