网络异常,图片无法展示
|
题目描述
这是 LeetCode 上的 71. 简化路径 ,难度为 中等。
Tag : 「模拟」、「栈」
给你一个字符串 path
,表示指向某一文件或目录的 Unix
风格 绝对路径 (以 '/'
开头),请你将其转化为更加简洁的规范路径。
在 Unix
风格的文件系统中,一个点(.
)表示当前目录本身;此外,两个点
(..
) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,'//'
)都被视为单个斜杠 '/'
。 对于此问题,任何其他格式的点(例如,'...'
)均被视为文件/
目录名称。
请注意,返回的 规范路径 必须遵循下述格式:
- 始终以斜杠
'/'
开头。 - 两个目录名之间必须只有一个斜杠
'/'
。 - 最后一个目录名(如果存在)不能 以
'/'
结尾。 - 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含 '
.'
或'..'
)。
返回简化后得到的 规范路径。
示例 1:
输入:path = "/home/" 输出:"/home" 解释:注意,最后一个目录名后面没有斜杠。 复制代码
示例 2:
输入:path = "/../" 输出:"/" 解释:从根目录向上一级是不可行的,因为根目录是你可以到达的最高级。 复制代码
示例 3:
输入:path = "/home//foo/" 输出:"/home/foo" 解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。 复制代码
示例 4:
输入:path = "/a/./b/../../c/" 输出:"/c" 复制代码
提示:
- 1 <= path.length <= 30001<=path.length<=3000
path
由英文字母,数字,'.'
,'/'
或'_'
组成。path
是一个有效的Unix
风格绝对路径。
模拟
根据题意,使用栈进行模拟即可。
具体的,从前往后处理 path
,每次以 item
为单位进行处理(有效的文件名),根据 item
为何值进行分情况讨论:
item
为有效值 :存入栈中;item
为..
:弹出栈顶元素(若存在);item
为.
:不作处理。
代码:
class Solution { public String simplifyPath(String path) { Deque<String> d = new ArrayDeque<>(); int n = path.length(); for (int i = 1; i < n; ) { if (path.charAt(i) == '/' && ++i >= 0) continue; int j = i + 1; while (j < n && path.charAt(j) != '/') j++; String item = path.substring(i, j); if (item.equals("..")) { if (!d.isEmpty()) d.pollLast(); } else if (!item.equals(".")) { d.addLast(item); } i = j; } StringBuilder sb = new StringBuilder(); while (!d.isEmpty()) sb.append("/" + d.pollFirst()); return sb.length() == 0 ? "/" : sb.toString(); } } 复制代码
- 时间复杂度:O(n)O(n)
- 空间复杂度:O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.71
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。