Simplify Path

Problem Description

Given an absolute path for a Unix-style file system, which begins with a slash '/', transform it to the simplified canonical path.

In a Unix-style file system rules:

• A single period '.' refers to the current directory.
• A double period '..' moves the directory up a level.
• Multiple consecutive slashes (e.g. '//') are treated as a single slash '/'.
• Any other format of periods (e.g. '...') are treated as file/directory names.

The canonical path should have the following format:

• The path starts with a single slash '/'.
• Any two directories are separated by a single slash '/'.
• The path does not end with a trailing '/'.
• The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Examples

Constraints

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

Splitting and Traversal Stack

To resolve relative directory markers like . and .., we can split the path by slashes /. This gives us a list of directory names and tokens. We use a stack to track our current position in the directory tree. We iterate through the tokens:

• If the token is empty or a single period ., we do nothing (it represents the current directory).
• If the token is a double period .., we move up a level by popping from the stack (if it is not already empty).
• For any other token, it represents a directory name; we push it onto the stack. Finally, we join the directories in the stack with a leading slash.

Solution 1: Directory Traversal Stack

Split the path by slashes and use a stack to resolve file system levels.

import java.util.Stack;

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

        for (String token : tokens) {
            if (token.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop(); // move up one directory
                }
            } else if (!token.equals("") && !token.equals(".")) {
                stack.push(token); // push directory name
            }
        }

        if (stack.isEmpty()) {
            return "/";
        }

        StringBuilder sb = new StringBuilder();
        for (String dir : stack) {
            sb.append("/").append(dir);
        }
        return sb.toString();
    }
}

class Solution:
    def simplifyPath(self, path: str) -> str:
        tokens = path.split('/')
        stack = []
        
        for token in tokens:
            if token == "..":
                if stack:
                    stack.pop()  # move up one directory
            elif token and token != ".":
                stack.append(token)  # push directory name
                
        return "/" + "/".join(stack)

#include <string>
#include <vector>
#include <sstream>

class Solution {
public:
    std::string simplifyPath(std::string path) {
        std::vector<std::string> stack;
        std::stringstream ss(path);
        std::string token;

        while (std::getline(ss, token, '/')) {
            if (token == "..") {
                if (!stack.empty()) {
                    stack.pop_back(); // move up one directory
                }
            } else if (!token.empty() && token != ".") {
                stack.push_back(token); // push directory name
            }
        }

        if (stack.empty()) return "/";

        std::string result = "";
        for (const std::string& dir : stack) {
            result += "/" + dir;
        }
        return result;
    }
};

Complexity Analysis

• Time Complexity: O(n) where n is the length of the path, since we split the string and visit each token once.
• Space Complexity: O(n) auxiliary space to store path tokens in the stack.

Where It Breaks

If the path contains symbolic links or circular references (e.g. files pointing to their parents via loop links), resolving it strictly using string analysis is not sufficient, and we must query the file system. Within the problem constraints, however, it is a pure string-resolution task.

Common Mistakes

• Incorrect check conditions: Forgetting to ignore empty tokens. Multiple consecutive slashes like /// will result in empty strings after splitting, which must be ignored.
• Popping from an empty stack: Attempting to pop when a .. is found at the root level, which causes a stack underflow exception. You must check if the stack is not empty before popping.

Frequently Asked Questions

Why does split(”/”) result in empty strings? Consecutive slashes (e.g., //) do not contain characters between them. Splitting by / treats the empty gap as an empty string "" token.

How does this handle three dots ”…”? Three dots are treated as a regular directory name and pushed onto the stack as is. Only . and .. have special behavior.

← All Problems