Simplify Path

medium stack string

Problem

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path. In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

Input"/home//foo/./bar/../baz/"

Output"/home/foo/baz"

'.' is dropped, '..' undoes 'bar', empty segments collapse.

path

def simplify_path(path):
    stack = []
    for part in path.split("/"):
        if part in ("", "."):
            continue
        if part == "..":
            if stack:
                stack.pop()
        else:
            stack.append(part)
    return "/" + "/".join(stack)

function simplifyPath(path) {
  const stack = [];
  for (const part of path.split("/")) {
    if (part === "" || part === ".") continue;
    if (part === "..") {
      if (stack.length) stack.pop();
    } else {
      stack.push(part);
    }
  }
  return "/" + stack.join("/");
}

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        for (String part : path.split("/")) {
            if (part.isEmpty() || part.equals(".")) continue;
            if (part.equals("..")) {
                if (!stack.isEmpty()) stack.pop();
            } else {
                stack.push(part);
            }
        }
        StringBuilder sb = new StringBuilder();
        Iterator<String> it = stack.descendingIterator();
        while (it.hasNext()) sb.append("/").append(it.next());
        return sb.length() == 0 ? "/" : sb.toString();
    }
}

string simplifyPath(string path) {
    vector<string> stack;
    string part;
    stringstream ss(path);
    while (getline(ss, part, '/')) {
        if (part.empty() || part == ".") continue;
        if (part == "..") { if (!stack.empty()) stack.pop_back(); }
        else stack.push_back(part);
    }
    string out;
    for (auto& p : stack) out += "/" + p;
    return out.empty() ? "/" : out;
}

Explanation

A Unix path is just directory names separated by slashes, with two special tokens: . means "stay here" and .. means "go up one level". A stack of directory names models exactly how you walk in and out of folders.

First we split the path on /. This gives us a list of parts, some of which may be empty (from // or trailing slashes). We then walk the parts with three simple rules.

An empty string or "." is skipped — it changes nothing. A ".." means go up, so we pop the last directory off the stack (if any). Anything else is a real directory name, so we push it.

Example: "/a/./b/../../c/" splits into parts a, ., b, .., .., c (plus empties). Push a, skip ., push b → [a, b]. First .. pops b → [a]; second .. pops a → []. Push c → [c].

Finally we join the stack with slashes and prepend a leading /, giving the canonical path "/c".

Time: O(n) Space: O(n)