# Simplify Path
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/simplify-path)
Canonical: https://scaleengineer.com/dsa/problems/simplify-path
**Data structures:** String, Stack
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Grab](https://scaleengineer.com/companies/grab), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Visa](https://scaleengineer.com/companies/visa), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Capital One](https://scaleengineer.com/companies/capital-one), [Tesla](https://scaleengineer.com/companies/tesla), [Citadel](https://scaleengineer.com/companies/citadel), [Gojek](https://scaleengineer.com/companies/gojek), [Roku](https://scaleengineer.com/companies/roku), [Upstart](https://scaleengineer.com/companies/upstart), [Harness](https://scaleengineer.com/companies/harness), [OpenAI](https://scaleengineer.com/companies/openai), [Patreon](https://scaleengineer.com/companies/patreon)
---
## Problem
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 = "/home/"

**Output:** "/home"

**Explanation:**

The trailing slash should be removed.

**Example 2:**

**Input:** path = "/home//foo/"

**Output:** "/home/foo"

**Explanation:**

Multiple consecutive slashes are replaced by a single one.

**Example 3:**

**Input:** path = "/home/user/Documents/../Pictures"

**Output:** "/home/user/Pictures"

**Explanation:**

A double period `".."` refers to the directory up a level (the parent directory).

**Example 4:**

**Input:** path = "/../"

**Output:** "/"

**Explanation:**

Going one level up from the root directory is not possible.

**Example 5:**

**Input:** path = "/.../a/../b/c/../d/./"

**Output:** "/.../b/d"

**Explanation:**

`"..."` is a valid name for a directory in this problem.

**Constraints:**

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

# Approaches
## Using String Split and Stack
This approach simplifies the path by first splitting the input string by the '/' delimiter to get all the directory/file components. It then uses a stack to process these components according to the rules of a Unix-style file system. Finally, it reconstructs the canonical path from the elements remaining in the stack.
**Time:** O(N), where N is the length of the input path string. Splitting, iterating, and joining are all linear operations. · **Space:** O(N), where N is the length of the input path. This space is used for the components array from `split()` and for the stack.
**Pros:** Conceptually simple and easy to understand.; Implementation is straightforward using built-in string and collection functionalities.
**Cons:** The `split()` method can be less performant as it creates an intermediate array of strings, which consumes extra memory.; Regular expression processing in `split()` might add a slight performance overhead compared to manual parsing.
### Explanation
The core idea is to treat the path as a sequence of directory operations. A forward navigation into a directory is like pushing onto a stack, and navigating up with '..' is like popping from the stack.

We can easily get all the directory components by splitting the input path string by the slash character. A `Deque` (Double-Ended Queue) implemented as a `LinkedList` is an excellent choice for a stack in Java.

After splitting the path, we iterate through each component.
- If a component is '..', we pop from our stack, but only if it's not empty (as we can't go above the root directory).
- If a component is '.' (current directory) or an empty string (resulting from multiple slashes like '//'), we ignore it.
- Otherwise, the component is a valid directory name, and we push it onto the stack.

Once all components are processed, we build the final canonical path by joining the elements in the stack with a '/' and prepending a leading '/'. If the stack is empty, it means the path simplifies to the root, so we return '/'.

Here is the Java implementation:
```java
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public String simplifyPath(String path) {
        // Use a Deque to simulate the stack of directory names
        Deque<String> stack = new LinkedList<>();
        
        // Split the path by one or more slashes. This handles cases like "//"
        String[] components = path.split("/+");
        
        for (String component : components) {
            if (component.equals("..")) {
                // If \"..\" is encountered, pop from stack if not empty
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }
            } else if (!component.isEmpty() && !component.equals(".")) {
                // If it's a valid directory name, push it onto the stack
                // We check for non-empty to ignore components from leading/trailing slashes
                stack.addLast(component);
            }
            // Ignore \".\" and empty components
        }
        
        // If the stack is empty, the result is the root directory \"/\"
        if (stack.isEmpty()) {
            return "/";
        }
        
        // Join the components in the stack with \"/\" and prepend a \"/\"
        return "/" + String.join("/", stack);
    }
}
```
### Algorithm
- Split the input `path` string by the `/` character (or `/+` regex for multiple slashes).
- Initialize a stack (e.g., a `Deque`).
- Iterate through each component from the split result:
  - If the component is `..`, pop from the stack if it's not empty.
  - If the component is not `.` and not empty, push it onto the stack.
  - Otherwise, ignore the component.
- After the loop, join the elements in the stack with `/` as a separator.
- Prepend a `/` to the joined string.
- If the stack was empty, return `/`.

## Manual Parsing with a Stack
This approach improves upon the first one by avoiding the `split()` method. It manually iterates through the input path string to identify the components between slashes. This avoids the overhead of creating an intermediate array of components, making it more efficient in terms of both time and space, although the asymptotic complexity remains the same.
**Time:** O(N), where N is the length of the path. We iterate through the string once. · **Space:** O(N), for the stack. The space for the `StringBuilder` is reused and is proportional to the maximum length of a component.
**Pros:** More efficient as it avoids creating an intermediate array of strings from `split()`.; Lower memory overhead.; Provides fine-grained control over the parsing logic.
**Cons:** The implementation is slightly more complex than the `split()`-based approach.; Requires careful manual handling of component boundaries.
### Explanation
Instead of pre-processing the entire string with `split()`, we can parse it on the fly. We iterate through the path character by character, building up each component name. A component is defined as the sequence of characters between two slashes.

We use a `StringBuilder` to accumulate the characters of the current component. When we encounter a `/`, it signals the end of the current component. We then process this component just as in the previous approach: push for a directory name, pop for `..`, and ignore for `.` or empty.

To simplify the logic, it's helpful to append a `/` to the input path. This ensures that the last component is always followed by a slash, so we don't need special code to handle it after the loop finishes.

This method avoids creating a potentially large intermediate array of strings, leading to better memory usage and potentially faster execution time.

Here is the Java implementation:
```java
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new LinkedList<>();
        StringBuilder componentBuilder = new StringBuilder();
        
        // Append a slash to handle the last component easily
        String processingPath = path + "/";

        for (char c : processingPath.toCharArray()) {
            if (c == '/') {
                if (componentBuilder.length() > 0) {
                    String component = componentBuilder.toString();
                    if (component.equals("..")) {
                        if (!stack.isEmpty()) {
                            stack.pollLast();
                        }
                    } else if (!component.equals(".")) {
                        stack.addLast(component);
                    }
                    // Reset builder for the next component
                    componentBuilder.setLength(0);
                }
            } else {
                componentBuilder.append(c);
            }
        }

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

        return "/" + String.join("/", stack);
    }
}
```
### Algorithm
- Initialize a stack (e.g., a `Deque`) and a `StringBuilder`.
- Append a `/` to the input `path` to ensure the last component is processed.
- Iterate through the modified path character by character:
  - If the character is not `/`, append it to the `StringBuilder`.
  - If the character is `/`, it marks the end of a component.
    - Process the string built in the `StringBuilder`.
    - If it's `..`, pop from the stack.
    - If it's not `.` and not empty, push to the stack.
    - Reset the `StringBuilder`.
- After the loop, build the final path from the stack as in the previous approach.

# Solutions
### CSharp

```csharp
public class Solution {
    public string SimplifyPath(string path) {
        var stk = new Stack < string > ();
        foreach(var s in path.Split('/')) {
            if (s == "" || s == ".") {
                continue;
            }
            if (s == "..") {
                if (stk.Count > 0) {
                    stk.Pop();
                }
            } else {
                stk.Push(s);
            }
        }
        var sb = new StringBuilder();
        while (stk.Count > 0) {
            sb.Insert(0, "/" + stk.Pop());
        }
        return sb.Length == 0 ? "/" : sb.ToString();
    }
}
```

### Java

```java
class Solution {
public
  String simplifyPath(String path) {
    Deque<String> stk = new ArrayDeque<>();
    for (String s : path.split("/")) {
      if ("".equals(s) || ".".equals(s)) {
        continue;
      }
      if ("..".equals(s)) {
        stk.pollLast();
      } else {
        stk.offerLast(s);
      }
    }
    return "/" + String.join("/", stk);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string simplifyPath(string path) {
    deque<string> stk;
    stringstream ss(path);
    string t;
    while (getline(ss, t, '/')) {
      if (t == "" || t == ".") {
        continue;
      }
      if (t == "..") {
        if (!stk.empty()) {
          stk.pop_back();
        }
      } else {
        stk.push_back(t);
      }
    }
    if (stk.empty()) {
      return "/";
    }
    string ans;
    for (auto &s : stk) {
      ans += "/" + s;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def simplifyPath(self, path: str) -> str: stk = [] for s in path . split('/'): if not s or s == '.': continue if s == '..': if stk: stk . pop() else: stk . append(s) return '/' + '/' . join(stk)

```