Skip to content

Commit a61ce03

Browse files
coderbeancoderbean
committed
0071. Simplify Path
1 parent bed9899 commit a61ce03

4 files changed

Lines changed: 230 additions & 0 deletions

File tree

‎markdown/0071. Simplify Path.md‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
### [71\. Simplify Path](https://leetcode.com/problems/simplify-path/)
2+
3+
Difficulty: **Medium**
4+
5+
6+
Given an **absolute path** for a file (Unix-style), simplify it. Or in other words, convert it to the **canonical path**.
7+
8+
In a UNIX-style file system, a period `.` refers to the current directory. Furthermore, a double period `..` moves the directory up a level. For more information, see: 
9+
10+
Note that the returned canonical path must always begin with a slash `/`, and there must be only a single slash `/` between two directory names. The last directory name (if it exists) **must not** end with a trailing `/`. Also, the canonical path must be the **shortest** string representing the absolute path.
11+
12+
**Example 1:**
13+
14+
```
15+
Input: "/home/"
16+
Output: "/home"
17+
Explanation: Note that there is no trailing slash after the last directory name.
18+
```
19+
20+
**Example 2:**
21+
22+
```
23+
Input: "/../"
24+
Output: "/"
25+
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
26+
```
27+
28+
**Example 3:**
29+
30+
```
31+
Input: "/home//foo/"
32+
Output: "/home/foo"
33+
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
34+
```
35+
36+
**Example 4:**
37+
38+
```
39+
Input: "/a/./b/../../c/"
40+
Output: "/c"
41+
```
42+
43+
**Example 5:**
44+
45+
```
46+
Input: "/a/../../b/../c//.//"
47+
Output: "/c"
48+
```
49+
50+
**Example 6:**
51+
52+
```
53+
Input: "/a//b////c/d//././/.."
54+
Output: "/a/b/c"
55+
```
56+
57+
58+
#### Solution
59+
60+
Language: **Java**
61+
62+
```java
63+
class Solution {
64+
   public String simplifyPath(String path) {
65+
       String[] split = path.split("/");
66+
       Deque<String> strings = new LinkedList<>(); // 使用双端队列
67+
       for (String s : split) {
68+
           if (!s.equals("") && !s.equals(".")) {
69+
               if (s.equals("..")) {
70+
                   if (!strings.isEmpty()) {
71+
                       strings.pop(); // 双端队列可以用作栈，返回上一层目录
72+
                  }
73+
              } else {
74+
                   strings.push(s); // 双端队列压栈写入头部元素
75+
              }
76+
          }
77+
      }
78+
       if (strings.isEmpty()) {
79+
           return "/";
80+
      }
81+
       StringBuilder stringBuilder = new StringBuilder();
82+
       while (!strings.isEmpty()) {
83+
           stringBuilder.append("/");
84+
           stringBuilder.append(strings.pollLast()); // 出尾部元素
85+
      }
86+
       return stringBuilder.toString();
87+
  }
88+
}
89+
```
90+
![](https://raw.githubusercontent.com/PicGoBed/PicBed/master/20190721232339.png)

‎src/main/java/leetcode/_71_/Main.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package leetcode._71_;
2+
3+
import java.util.Stack;
4+
5+
/**
6+
* Created by zhangbo54 on 2019-03-04.
7+
*/
8+
public class Main {
9+
public static void main(String[] args) {
10+
Solution solution = new Solution();
11+
System.out.println(solution.simplifyPath("/home/"));
12+
System.out.println(solution.simplifyPath("/../"));
13+
System.out.println(solution.simplifyPath("/home//foo/"));
14+
System.out.println(solution.simplifyPath("/a/./b/../../c/"));
15+
System.out.println(solution.simplifyPath("/a/../../b/../c//.//"));
16+
System.out.println(solution.simplifyPath("/a//b////c/d//././/.."));
17+
}
18+
}
19+

‎src/main/java/leetcode/_71_/Solution.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package leetcode._71_;
2+
3+
import java.util.Deque;
4+
import java.util.LinkedList;
5+
6+
class Solution {
7+
public String simplifyPath(String path) {
8+
String[] split = path.split("/");
9+
Deque<String> strings = new LinkedList<>(); // 使用双端队列
10+
for (String s : split) {
11+
if (!s.equals("") && !s.equals(".")) {
12+
if (s.equals("..")) {
13+
if (!strings.isEmpty()) {
14+
strings.pop(); // 双端队列可以用作栈，返回上一层目录
15+
}
16+
} else {
17+
strings.push(s); // 双端队列压栈写入头部元素
18+
}
19+
}
20+
}
21+
if (strings.isEmpty()) {
22+
return "/";
23+
}
24+
StringBuilder stringBuilder = new StringBuilder();
25+
while (!strings.isEmpty()) {
26+
stringBuilder.append("/");
27+
stringBuilder.append(strings.pollLast()); // 出尾部元素
28+
}
29+
return stringBuilder.toString();
30+
}
31+
}

‎src/main/java/leetcode/_71_/solution.md‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
### [71\. Simplify Path](https://leetcode.com/problems/simplify-path/)
2+
3+
Difficulty: **Medium**
4+
5+
6+
Given an **absolute path** for a file (Unix-style), simplify it. Or in other words, convert it to the **canonical path**.
7+
8+
In a UNIX-style file system, a period `.` refers to the current directory. Furthermore, a double period `..` moves the directory up a level. For more information, see: 
9+
10+
Note that the returned canonical path must always begin with a slash `/`, and there must be only a single slash `/` between two directory names. The last directory name (if it exists) **must not** end with a trailing `/`. Also, the canonical path must be the **shortest** string representing the absolute path.
11+
12+
**Example 1:**
13+
14+
```
15+
Input: "/home/"
16+
Output: "/home"
17+
Explanation: Note that there is no trailing slash after the last directory name.
18+
```
19+
20+
**Example 2:**
21+
22+
```
23+
Input: "/../"
24+
Output: "/"
25+
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
26+
```
27+
28+
**Example 3:**
29+
30+
```
31+
Input: "/home//foo/"
32+
Output: "/home/foo"
33+
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
34+
```
35+
36+
**Example 4:**
37+
38+
```
39+
Input: "/a/./b/../../c/"
40+
Output: "/c"
41+
```
42+
43+
**Example 5:**
44+
45+
```
46+
Input: "/a/../../b/../c//.//"
47+
Output: "/c"
48+
```
49+
50+
**Example 6:**
51+
52+
```
53+
Input: "/a//b////c/d//././/.."
54+
Output: "/a/b/c"
55+
```
56+
57+
58+
#### Solution
59+
60+
Language: **Java**
61+
62+
```java
63+
class Solution {
64+
   public String simplifyPath(String path) {
65+
       String[] split = path.split("/");
66+
       Deque<String> strings = new LinkedList<>(); // 使用双端队列
67+
       for (String s : split) {
68+
           if (!s.equals("") && !s.equals(".")) {
69+
               if (s.equals("..")) {
70+
                   if (!strings.isEmpty()) {
71+
                       strings.pop(); // 双端队列可以用作栈，返回上一层目录
72+
                  }
73+
              } else {
74+
                   strings.push(s); // 双端队列压栈写入头部元素
75+
              }
76+
          }
77+
      }
78+
       if (strings.isEmpty()) {
79+
           return "/";
80+
      }
81+
       StringBuilder stringBuilder = new StringBuilder();
82+
       while (!strings.isEmpty()) {
83+
           stringBuilder.append("/");
84+
           stringBuilder.append(strings.pollLast()); // 出尾部元素
85+
      }
86+
       return stringBuilder.toString();
87+
  }
88+
}
89+
```
90+
![](https://raw.githubusercontent.com/PicGoBed/PicBed/master/20190721232339.png)

0 commit comments

Comments
 (0)