71. Simplify Path - Explanation

Description

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path.

The rules of a Unix-style file system are as follows:

A single period '.' represents the current directory.
A double period '..' represents the previous/parent directory.
Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'.
Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...' and '....' are valid directory or file names.

The simplified canonical path should follow these rules:

The path must start with a single slash '/'.
Directories within the path must be separated by exactly one slash '/'.
The path must not end with a slash '/', unless it is the root directory.
The path must not have any single or double periods ('.' and '..') used to denote current or parent directories.

Return the simplified canonical path.

Example 1:

Input: path = "/neetcode/practice//...///../courses"

Output: "/neetcode/practice/courses"

Example 2:

Input: path = "/..//"

Output: "/"

Example 3:

Input: path = "/..//_home/a/b/..///"

Output: "/_home/a"

Constraints:

1 <= path.length <= 3000
path consists of English letters, digits, period '.', slash '/' or '_'.
path is a valid absolute Unix path.

Topics

String Stack

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Stack Data Structure - Using push/pop operations to track directory hierarchy
String Parsing - Splitting strings by delimiters and handling edge cases like empty strings
Unix Path Semantics - Understanding that . means current directory and .. means parent directory

1. Stack - I

Intuition

A Unix-style path can contain special directory references: . means the current directory (stay in place), and .. means the parent directory (go up one level). Multiple slashes should be treated as a single separator. A stack is ideal here because navigating to a parent directory is just like popping from a stack, while entering a subdirectory is like pushing onto it.

Algorithm

Append a trailing / to ensure the last directory name is processed.
Iterate character by character, building up the current directory name.
When encountering a /:
- If the accumulated name is .., pop from the stack (if not empty).
- If the name is a valid directory (not empty and not .), push it onto the stack.
- Reset the current name.
Join the stack elements with / and prepend a leading / to form the canonical path.

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        cur = ""

        for c in path + "/":
            if c == "/":
                if cur == "..":
                    if stack:
                        stack.pop()
                elif cur != "" and cur != ".":
                    stack.append(cur)
                cur = ""
            else:
                cur += c

        return "/" + "/".join(stack)

public class Solution {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        StringBuilder cur = new StringBuilder();

        for (char c : (path + "/").toCharArray()) {
            if (c == '/') {
                if (cur.toString().equals("..")) {
                    if (!stack.isEmpty()) stack.pop();
                } else if (!cur.toString().equals("") && !cur.toString().equals(".")) {
                    stack.push(cur.toString());
                }
                cur.setLength(0);
            } else {
                cur.append(c);
            }
        }

        return "/" + String.join("/", stack);
    }
}

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> stack;
        string cur;

        for (char c : path + "/") {
            if (c == '/') {
                if (cur == "..") {
                    if (!stack.empty()) stack.pop_back();
                } else if (!cur.empty() && cur != ".") {
                    stack.push_back(cur);
                }
                cur.clear();
            } else {
                cur += c;
            }
        }

        string result = "/";
        for (int i = 0; i < stack.size(); ++i) {
            if (i > 0) result += "/";
            result += stack[i];
        }

        return result;
    }
};

class Solution {
    /**
     * @param {string} path
     * @return {string}
     */
    simplifyPath(path) {
        const stack = [];
        let cur = '';

        for (const c of path + '/') {
            if (c === '/') {
                if (cur === '..') {
                    if (stack.length) stack.pop();
                } else if (cur !== '' && cur !== '.') {
                    stack.push(cur);
                }
                cur = '';
            } else {
                cur += c;
            }
        }

        return '/' + stack.join('/');
    }
}

public class Solution {
    public string SimplifyPath(string path) {
        Stack<string> stack = new Stack<string>();
        string cur = "";

        foreach (char c in path + "/") {
            if (c == '/') {
                if (cur == "..") {
                    if (stack.Count > 0) stack.Pop();
                } else if (cur != "" && cur != ".") {
                    stack.Push(cur);
                }
                cur = "";
            } else {
                cur += c;
            }
        }

        var result = new List<string>(stack);
        result.Reverse();
        return "/" + string.Join("/", result);
    }
}

func simplifyPath(path string) string {
    stack := []string{}
    cur := ""

    for _, c := range path + "/" {
        if c == '/' {
            if cur == ".." {
                if len(stack) > 0 {
                    stack = stack[:len(stack)-1]
                }
            } else if cur != "" && cur != "." {
                stack = append(stack, cur)
            }
            cur = ""
        } else {
            cur += string(c)
        }
    }

    return "/" + strings.Join(stack, "/")
}

class Solution {
    fun simplifyPath(path: String): String {
        val stack = ArrayDeque<String>()
        var cur = StringBuilder()

        for (c in path + "/") {
            if (c == '/') {
                val s = cur.toString()
                if (s == "..") {
                    if (stack.isNotEmpty()) stack.removeLast()
                } else if (s != "" && s != ".") {
                    stack.addLast(s)
                }
                cur = StringBuilder()
            } else {
                cur.append(c)
            }
        }

        return "/" + stack.joinToString("/")
    }
}

class Solution {
    func simplifyPath(_ path: String) -> String {
        var stack = [String]()
        var cur = ""

        for c in path + "/" {
            if c == "/" {
                if cur == ".." {
                    if !stack.isEmpty { stack.removeLast() }
                } else if cur != "" && cur != "." {
                    stack.append(cur)
                }
                cur = ""
            } else {
                cur += String(c)
            }
        }

        return "/" + stack.joined(separator: "/")
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Stack - II

Intuition

Instead of processing character by character, we can split the path by / to get all the directory names at once. This simplifies the logic since we directly work with directory names rather than building them up. The same stack-based approach applies: push valid directories and pop on ...

Algorithm

Split the path string by / to get an array of parts.
For each part:
- If it equals .., pop from the stack (if not empty).
- If it is a valid directory name (not empty and not .), push it onto the stack.
Join the stack with / and prepend a leading / to return the simplified path.

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        paths = path.split("/")

        for cur in paths:
            if cur == "..":
                if stack:
                    stack.pop()
            elif cur != "" and cur != ".":
                stack.append(cur)

        return "/" + "/".join(stack)

public class Solution {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        String[] paths = path.split("/");

        for (String cur : paths) {
            if (cur.equals("..")) {
                if (!stack.isEmpty()) stack.pop();
            } else if (!cur.equals("") && !cur.equals(".")) {
                stack.push(cur);
            }
        }

        return "/" + String.join("/", stack);
    }
}

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> stack;
        string cur;
        stringstream ss(path);
        while (getline(ss, cur, '/')) {
            if (cur.empty()) continue;
            if (cur == "..") {
                if (!stack.empty()) stack.pop_back();
            } else if (!cur.empty() && cur != ".") {
                stack.push_back(cur);
            }
        }

        string result = "/";
        for (int i = 0; i < stack.size(); ++i) {
            if (i > 0) result += "/";
            result += stack[i];
        }

        return result;
    }
};

class Solution {
    /**
     * @param {string} path
     * @return {string}
     */
    simplifyPath(path) {
        const stack = [];
        const paths = path.split('/');

        for (const cur of paths) {
            if (cur === '..') {
                if (stack.length) {
                    stack.pop();
                }
            } else if (cur !== '' && cur !== '.') {
                stack.push(cur);
            }
        }

        return '/' + stack.join('/');
    }
}

public class Solution {
    public string SimplifyPath(string path) {
        Stack<string> stack = new Stack<string>();
        string[] parts = path.Split('/');

        foreach (string part in parts) {
            if (part == "..") {
                if (stack.Count > 0) {
                    stack.Pop();
                }
            } else if (part != "" && part != ".") {
                stack.Push(part);
            }
        }

        var result = new List<string>(stack);
        result.Reverse();
        return "/" + string.Join("/", result);
    }
}

func simplifyPath(path string) string {
    stack := []string{}
    paths := strings.Split(path, "/")

    for _, cur := range paths {
        if cur == ".." {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]
            }
        } else if cur != "" && cur != "." {
            stack = append(stack, cur)
        }
    }

    return "/" + strings.Join(stack, "/")
}

class Solution {
    fun simplifyPath(path: String): String {
        val stack = ArrayDeque<String>()
        val paths = path.split("/")

        for (cur in paths) {
            if (cur == "..") {
                if (stack.isNotEmpty()) stack.removeLast()
            } else if (cur != "" && cur != ".") {
                stack.addLast(cur)
            }
        }

        return "/" + stack.joinToString("/")
    }
}

class Solution {
    func simplifyPath(_ path: String) -> String {
        var stack = [String]()
        let paths = path.split(separator: "/")

        for cur in paths {
            let part = String(cur)
            if part == ".." {
                if !stack.isEmpty { stack.removeLast() }
            } else if part != "" && part != "." {
                stack.append(part)
            }
        }

        return "/" + stack.joined(separator: "/")
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Popping from an Empty Stack on ".."

When encountering .., you should only pop from the stack if it is non-empty. Attempting to pop from an empty stack causes runtime errors in some languages, and logically, going to the parent of the root directory should simply stay at the root. Forgetting this check leads to crashes or incorrect path construction.

Treating "." and ".." as Valid Directory Names

The single dot . means "current directory" and should be ignored, while .. means "parent directory" and triggers a pop operation. A common mistake is pushing these onto the stack as if they were regular directory names, resulting in paths like /home/./user/../.. instead of the simplified /home.

Not Handling Multiple Consecutive Slashes

Paths like //home///user should be treated the same as /home/user. When splitting by / or processing character by character, multiple consecutive slashes produce empty strings. Failing to skip these empty strings can result in incorrect behavior or extra slashes in the output.