Simplify Path
Problem
Given a string path representing an absolute Unix-style file path, return the simplified canonical path.
- 1 ≤ path.length ≤ 3000
- path consists of English letters, digits, period '.', slash '/' or '_'
- path is a valid absolute Unix path
Example
path = "/a/./b/../../c/""/c"Walk through the example path step by step. 1) Start with the input: path = "/a/./b/../../c/". 2) Split by '/' to get raw parts: ["", "a", ".", "b", "..", "..", "c", ""]. The empty strings come from leading, trailing, and double slashes. 3) Initialize an empty stack to represent the current directory path. 4) Process each part in order: - "" → ignore (no directory) - "a" → push onto stack → ["a"] - "." → current directory, ignore - "b" → push onto stack → ["a", "b"] - ".." → go up one level, pop → ["a"] - ".." → go up again, pop → [] - "c" → push onto stack → ["c"] - "" → ignore 5) After processing all parts, the stack holds ["c"], which describes the simplified path from root. 6) Join the stack with '/' and prefix with '/', giving the canonical path "/c".
Approach
Straightforward Solution
A naive approach would try to simplify the path by manually editing the string, repeatedly removing dot and dot-dot segments and collapsing slashes. This is messy, easy to get wrong around edge cases like multiple slashes or long chains of parent moves, and less efficient than a single linear pass with a stack.
Core Observation
The path can be decomposed into components separated by '/', where '.' means current directory (no change), '..' means move up one directory (pop last), and other names mean move into a subdirectory (push). The problem reduces to processing these components in order and maintaining a stack to represent the current directory path.
Path to Optimal
Splitting the path by '/' yields components that can be processed sequentially. Using a stack to track directory names allows easy handling of '..' by popping the last directory. Ignoring empty strings and '.' components simplifies the logic. After processing all components, joining the stack with '/' and prefixing with '/' produces the canonical path.
Optimal Approach
Split the input path by '/'. Iterate over each component: skip empty strings and '.', pop from the stack if '..' and stack is not empty, otherwise push the component. Finally, join the stack with '/' and prefix with '/' to form the simplified path. This approach is clean, efficient, and handles all edge cases.
Time
O(n)
Splitting the path and iterating through each component is O(n), where n is the length of the path string. Each component is processed once, and stack operations are O(1) amortized.
Space
O(n)
The stack stores directory names, which in the worst case can be all components of the path, leading to O(n) auxiliary space. The output string also requires O(n) space but is not counted as auxiliary.
Pattern Spotlight
Stack (Path Simplification)
Use a stack to simulate directory traversal: push directory names, pop on '..', and ignore '.' or empty components, enabling linear-time canonical path construction.
Solution
| 1 | class Solution:
|
| 2 | def simplifyPath(self, path: str) -> str:
|
| 3 | parts = path.split("/")
|
| 4 | stack = []
|
| 5 |
|
| 6 | for part in parts:
|
| 7 | if part == "" or part == ".":
|
| 8 | continue
|
| 9 | elif part == "..":
|
| 10 | if stack:
|
| 11 | stack.pop()
|
| 12 | else:
|
| 13 | stack.append(part)
|
| 14 |
|
| 15 | return "/" + "/".join(stack) |
| 1 | import java.util.Stack; |
| 2 | |
| 3 | public class Solution { |
| 4 | public String simplifyPath(String path) { |
| 5 | String[] parts = path.split("/"); |
| 6 | Stack<String> stack = new Stack<>(); |
| 7 | |
| 8 | for (String part : parts) { |
| 9 | if (part.equals("") || part.equals(".")) { |
| 10 | continue; |
| 11 | } else if (part.equals("..")) { |
| 12 | if (!stack.isEmpty()) { |
| 13 | stack.pop(); |
| 14 | } |
| 15 | } else { |
| 16 | stack.push(part); |
| 17 | } |
| 18 | } |
| 19 | |
| 20 | StringBuilder result = new StringBuilder(); |
| 21 | for (String dir : stack) { |
| 22 | result.append("/").append(dir); |
| 23 | } |
| 24 | |
| 25 | return result.length() > 0 ? result.toString() : "/"; |
| 26 | } |
| 27 | } |
| 1 | #include <string> |
| 2 | #include <vector> |
| 3 | #include <sstream> |
| 4 | #include <stack> |
| 5 | |
| 6 | using namespace std; |
| 7 | |
| 8 | class Solution { |
| 9 | public: |
| 10 | string simplifyPath(string path) { |
| 11 | vector<string> parts; |
| 12 | stringstream ss(path); |
| 13 | string item; |
| 14 | while (getline(ss, item, '/')) { |
| 15 | parts.push_back(item); |
| 16 | } |
| 17 | |
| 18 | stack<string> stk; |
| 19 | for (const string& part : parts) { |
| 20 | if (part.empty() || part == ".") { |
| 21 | continue; |
| 22 | } else if (part == "..") { |
| 23 | if (!stk.empty()) { |
| 24 | stk.pop(); |
| 25 | } |
| 26 | } else { |
| 27 | stk.push(part); |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | vector<string> reversed; |
| 32 | while (!stk.empty()) { |
| 33 | reversed.push_back(stk.top()); |
| 34 | stk.pop(); |
| 35 | } |
| 36 | reverse(reversed.begin(), reversed.end()); |
| 37 | |
| 38 | string result = ""; |
| 39 | for (const string& dir : reversed) { |
| 40 | result += "/" + dir; |
| 41 | } |
| 42 | |
| 43 | return result.empty() ? "/" : result; |
| 44 | } |
| 45 | }; |
| 1 | var simplifyPath = function(path) { |
| 2 | const parts = path.split('/'); |
| 3 | const stack = []; |
| 4 | |
| 5 | for (const part of parts) { |
| 6 | if (part === '' || part === '.') { |
| 7 | continue; |
| 8 | } else if (part === '..') { |
| 9 | if (stack.length > 0) { |
| 10 | stack.pop(); |
| 11 | } |
| 12 | } else { |
| 13 | stack.push(part); |
| 14 | } |
| 15 | } |
| 16 | |
| 17 | return '/' + stack.join('/'); |
| 18 | }; |
Step-by-Step Solution
Split Path and Initialize Stack for Directory Tracking
| 3 | parts = path.split("/")
|
| 4 | stack = []
|
Objective
To decompose the input path into manageable components and prepare a stack to track the current directory state.
Key Insight
Splitting the path by '/' isolates directory names and special symbols ('.', '..'). An empty string or '.' means no directory change and can be skipped. The stack will represent the current path state, allowing efficient push/pop operations corresponding to moving into or out of directories.
Interview Quick-Check
Core Logic
Splitting by '/' transforms the path string into discrete components that can be processed sequentially.
Common Pitfalls & Bugs
Treating empty components from leading, trailing, or repeated slashes as real directory names instead of skipping them.
Process Each Path Component to Update Directory Stack
| 6 | for part in parts:
|
| 7 | if part == "" or part == ".":
|
| 8 | continue
|
| 9 | elif part == "..":
|
| 10 | if stack:
|
| 11 | stack.pop()
|
| 12 | else:
|
| 13 | stack.append(part)
|
Objective
To iterate through each component and update the stack to reflect the current directory after applying Unix path rules.
Key Insight
Ignoring empty strings and '.' components avoids unnecessary operations. When encountering '..', popping from the stack simulates moving up one directory, but only if the stack is not empty to avoid moving above root. Otherwise, pushing the component adds a new directory to the path. This logic directly models Unix path traversal semantics.
Interview Quick-Check
Core Logic
The stack simulates directory traversal: push directory names, pop on '..', and skip '.' or empty components.
State & Boundaries
Check if the stack is non-empty before popping to prevent moving above the root directory.
Common Pitfalls & Bugs
Popping from an empty stack when processing '..', which incorrectly moves “above” the root directory or causes an error.
Construct and Return the Canonical Path from Stack
| 15 | return "/" + "/".join(stack) |
Objective
To build the final simplified path string from the stack contents.
Key Insight
Joining the stack elements with '/' reconstructs the path without redundant slashes or special components. Prefixing with '/' ensures the path is absolute. This step finalizes the transformation from the stack representation back to the required string format.
Interview Quick-Check
Core Logic
Joining stack elements with '/' and prefixing with '/' produces the canonical absolute path.
Common Pitfalls & Bugs
Forgetting to prefix with '/' or incorrectly joining components can produce invalid paths.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
elif part == "..":Check if the component is '..', indicating moving up one directory.
Recognizing '..' is critical to correctly simulate moving to the parent directory by popping the last directory from the stack.
if stack:Check if the stack is not empty before popping.
Preventing popping from an empty stack avoids invalid path states and respects the root directory boundary.
stack.pop()Pop the last directory from the stack to move up one level.
This operation simulates the effect of '..' in Unix paths, removing the most recent directory from the current path.
return "/" + "/".join(stack)Join the stack components with '/' and prefix with '/' to form the canonical path.
This constructs the final simplified absolute path string, ensuring correct formatting without redundant slashes or special components.
parts = path.split("/")Split the input path string by '/' to get individual components.
Splitting by '/' isolates directory names and special symbols, enabling sequential processing of each path segment.
stack = []Initialize an empty stack to track the current directory path.
The stack models the directory traversal state, allowing efficient push/pop operations corresponding to moving into or out of directories.
stack.append(part)Push the current directory component onto the stack.
Adding a valid directory name to the stack represents moving into a subdirectory, building the simplified path incrementally.
if part == "" or part == ".":Skip empty strings and '.' components which represent no directory change.
Ignoring these components prevents unnecessary stack operations and maintains correctness by not altering the current directory.
else:Use the final else branch to route normal directory components toward being added to the stack.
This else branch captures all components that are not no-ops ("" or ".") and not parent moves (".."). Directing those cases here ensures that only genuine directory names flow into the push step, keeping the stack a clean representation of the current path.
continueContinue to the next iteration if the component is empty or '.'.
This control flow ensures that no stack modification occurs for no-op components, preserving the current directory state.
for part in parts:Iterate over each component in the split path.
Sequential processing of components is necessary to apply Unix path simplification rules in order.
Test Your Understanding
Why is a stack the appropriate data structure for simplifying the Unix path?
Because directory traversal with '..' requires reversing the last directory step, which is naturally modeled by pushing directory names onto a stack and popping when '..' is encountered, reflecting moving up one directory.
Related Problems
Stacks pattern
Don't just read it. Drill it.
Reconstruct Simplify Path from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Simplify Path drill