Skip to content

simplify-path.md

Latest commit

 

History

History
488 lines (403 loc) · 12.5 KB

simplify-path.md

File metadata and controls

488 lines (403 loc) · 12.5 KB

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

  1. Append a trailing / to ensure the last directory name is processed.
  2. Iterate character by character, building up the current directory name.
  3. 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.
  4. Join the stack elements with / and prepend a leading / to form the canonical path.

::tabs-start

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

        for c in path + "/":
            if c == "/":
                cur = "".join(cur)
                if cur == "..":
                    if stack:
                        stack.pop()
                elif cur != "" and cur != ".":
                    stack.append(cur)
                cur = []
            else:
                cur.append(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: "/")
    }
}
impl Solution {
    pub fn simplify_path(path: String) -> String {
        let mut stack: Vec<String> = Vec::new();
        let mut cur = String::new();

        for c in path.chars().chain(std::iter::once('/')) {
            if c == '/' {
                if cur == ".." {
                    stack.pop();
                } else if !cur.is_empty() && cur != "." {
                    stack.push(cur.clone());
                }
                cur.clear();
            } else {
                cur.push(c);
            }
        }

        format!("/{}", stack.join("/"))
    }
}

::tabs-end

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

  1. Split the path string by / to get an array of parts.
  2. 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.
  3. Join the stack with / and prepend a leading / to return the simplified path.

::tabs-start

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: "/")
    }
}
impl Solution {
    pub fn simplify_path(path: String) -> String {
        let mut stack: Vec<&str> = Vec::new();

        for part in path.split('/') {
            match part {
                ".." => { stack.pop(); }
                "" | "." => {}
                _ => stack.push(part),
            }
        }

        format!("/{}", stack.join("/"))
    }
}

::tabs-end

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.