Resolve a Simplified Absolute File Path
Solve this Problempath, simplify it into its canonical form: collapse multiple consecutive slashes into one, drop every "." segment (it means "stay here"), and resolve every ".." segment by cancelling out the directory segment immediately before it.
Since ".." only ever needs to know the single most recently resolved segment — nothing deeper — a stackStackA LIFO (Last In, First Out) structure. Path resolution only ever needs to inspect or cancel the most recently added segment, never anything beneath it, which is exactly what a stack exposes for free. is the natural fit: push real directory names, skip "." entirely, and pop on "..". Rebuilding the resolved path from a string every time "..\" appears works but wastes effort re-deriving something a stack already knows in O(1) — its own top.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ path.length ≤ 40 - ◆
path is a valid absolute Unix-style path starting with '/' - ◆
Path segments are separated by '/', and may include '.' (current directory), '..' (parent directory), multiple consecutive slashes, or ordinary directory names of lowercase letters - ◆
The simplified path must not end with a trailing '/', unless it is the root "/" itself
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Re-derive the Resolved Path on Every ".."
BruteSplit the path into segments on '/', skipping empty segments and "." (both no-ops). For each remaining segment, append it to the resolved path so far — except for "..", which needs to cancel out the most recent real segment. To find that segment, re-split the resolved-path-so-far from scratch, drop its last piece, and rebuild it as a string. That re-split-and-rebuild costs O(current length) every single time a "..\" is encountered, and a path can contain many of them, making this O(n²) overall.
O(n²)O(n)1class Solution {
2 public String resolvePath(String path) {
3 String[] tokens = path.split("/");
4 String resolved = "";
5 for (String p : tokens) {
6 if (p.isEmpty() || p.equals(".")) continue;
7 if (p.equals("..")) {
8 String[] segs = resolved.split("/");
9 StringBuilder rebuilt = new StringBuilder();
10 int count = 0;
11 for (String seg : segs) if (!seg.isEmpty()) count++;
12 int kept = Math.max(0, count - 1);
13 int seen = 0;
14 for (String seg : segs) {
15 if (seg.isEmpty()) continue;
16 if (seen < kept) { rebuilt.append("/").append(seg); }
17 seen++;
18 }
19 resolved = rebuilt.toString();
20 } else {
21 resolved = resolved + "/" + p;
22 }
23 }
24 return resolved.isEmpty() ? "/" : resolved;
25 }
26}Optimal — Single Pass With a Segment Stack
OptimalSame tokenization, but keep the resolved segments on a stack instead of rebuilding a string. A real directory name pushes; a "." is skipped; a ".." pops (cancelling the most recent real segment) — all O(1), since the stack already knows exactly what its most recent element is, with no re-splitting required. After one pass over the tokens, join whatever remains on the stack with '/' to get the final resolved path.
O(n)O(n)1class Solution {
2 public String resolvePath(String path) {
3 Deque<String> stack = new ArrayDeque<>();
4 String[] tokens = path.split("/");
5 for (String p : tokens) {
6 if (p.isEmpty() || p.equals(".")) continue;
7 if (p.equals("..")) {
8 if (!stack.isEmpty()) stack.pollLast();
9 } else {
10 stack.addLast(p);
11 }
12 }
13 StringBuilder result = new StringBuilder();
14 for (String seg : stack) result.append("/").append(seg);
15 return result.length() == 0 ? "/" : result.toString();
16 }
17}