Course4all
Join us on telegram
Home/dsa/Stack/Simplify Path

Simplify Path

Master this topic with zero to advance depth.

Simplify Path

Given a Unix-style absolute path, simplify it to its canonical form.

Visual Representation

path = "/home//foo/../bar/" Tokens: ["home", "", "foo", "..", "bar"] 1. "home": Valid name. Push. Stack: ["home"] 2. "": Empty. Skip. 3. "foo": Valid name. Push. Stack: ["home", "foo"] 4. "..": Parent dir. Pop. Stack: ["home"] 5. "bar": Valid name. Push. Stack: ["home", "bar"] Canonical Path: "/home/bar"
Medium

Examples

Input: path = "/home//foo/"
Output: "/home/foo"
Input: path = "/../"
Output: "/"
Approach 1

Level I: Iterative Stack Processing (Natural Approach)

Intuition

Split the path by '/' into parts. Maintain a list acting as a stack: push valid directory names, pop for '..', skip '.' and empty parts. Join the stack with '/' prefixed by '/'.

⏱ O(N)💾 O(N)
java
import java.util.*;
public class Main {
    public static String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        for (String s : path.split("/")) {
            if (s.equals("..")) { if (!stack.isEmpty()) stack.pollLast(); }
            else if (!s.isEmpty() && !s.equals(".")) stack.addLast(s);
        }
        return "/" + String.join("/", stack);
    }
    public static void main(String[] args) { System.out.println(simplifyPath("/home//foo/../bar/")); }
}
Approach 2

Level II: Recursive Path Reduction

Intuition

Instead of using an explicit stack, we can process the path string repeatedly by removing the most 'reducible' parts. For example, replacing /./ with / and /directory_name/../ with /. This is less efficient but helpful for understanding the underlying LIFO structure of the path.

⏱ O(N^2) in the worst case (e.g., /a/a/a/a/../../../../)💾 O(N) for string copies during reduction.
java
public class Solution {
    public String simplifyPath(String path) {
        path = path.replaceAll("/+", "/");
        if (path.length() > 1 && path.endsWith("/")) path = path.substring(0, path.length() - 1);
        
        String oldPath = "";
        while (!path.equals(oldPath)) {
            oldPath = path;
            path = path.replaceAll("/[^/]+/\\.\\.(/|$)", "/");
            path = path.replaceAll("/\\.(/|$)", "/");
        }
        if (path.isEmpty()) return "/";
        if (path.length() > 1 && path.endsWith("/")) path = path.substring(0, path.length() - 1);
        if (!path.startsWith("/")) path = "/" + path;
        return path;
    }
}
Approach 3

Level III: Optimal (Stack Tokenization)

Intuition

Split the path by / and process each component. A stack maintains the valid directory structure. .. removes the last added directory, while . or empty strings are ignored. Any other string is a valid directory to be pushed.

⏱ O(N)💾 O(N)

Detailed Dry Run

PartActionStack Content
"home"Push["home"]
"foo"Push["home", "foo"]
".."Pop["home"]
"bar"Push["home", "bar"]
java
import java.util.*;

public class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        for (String s : path.split("/")) {
            if (s.equals("..")) {
                if (!stack.isEmpty()) stack.pop();
            } else if (!s.equals("") && !s.equals(".")) {
                stack.push(s);
            }
        }
        if (stack.isEmpty()) return "/";
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) res.append("/").append(stack.removeLast());
        return res.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.simplifyPath("/home//foo/../bar/")); // "/home/bar"
    }
}

⚠️ Common Pitfalls & Tips

Multiple slashes become one. .. at the root keeps you at the root. The trailing slash should be removed unless it's the root itself.

← Previous QuestionTrapping Rain Water
Next Question →Generate Parentheses