> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/simplify-path.md).

# 71. Simplify Path

### Description

Given an **absolute path** for a file (Unix-style), simplify it. Or in other words, convert it to the **canonical path**.

In a UNIX-style file system, a period `.` refers to the current directory. Furthermore, a double period `..` moves the directory up a level.

Note that the returned canonical path must always begin with a slash `/`, and there must be only a single slash `/` between two directory names. The last directory name (if it exists) **must not** end with a trailing `/`. Also, the canonical path must be the **shortest** string representing the absolute path.

### **Constraints**

### **Approach**

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/simplify-directory-path-unix-like/)
* [Leetcode](https://leetcode.com/problems/simplify-path/)
* [ProgramCreek](https://www.programcreek.com/2014/04/leetcode-simplify-path-java/)
* YouTube

### Examples

{% tabs %}
{% tab title="Example 1" %}
**Input:** "/home/"

**Output:** "/home"

**Explanation:** Note that there is no trailing slash after the last directory name.
{% endtab %}

{% tab title="Example 2" %}
**Input:** "/../"

**Output:** "/"

**Explanation:** Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
{% endtab %}

{% tab title="Example 3" %}
**Input:** "/home//foo/"

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

**Explanation:** In the canonical path, multiple consecutive slashes are replaced by a single one.
{% endtab %}

{% tab title="Example 4" %}
**Input:** "/a/./b/../../c/"

**Output:** "/c"
{% endtab %}

{% tab title="Example 5" %}
**Input:** "/a/../../b/../c//.//"

**Output:** "/c"
{% endtab %}

{% tab title="Example 6" %}
**Input:** "/a//b////c/d//././/.."

**Output:** "/a/b/c"
{% endtab %}
{% endtabs %}

### Solutions

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N) if there are N characters in the original path. 
 *    First, we spend O(N) trying to split the input path into components 
 *    and then we process each component one by one which is again an O(N) 
 *    operation. We can get rid of the splitting part and just string together
 *    the characters and form directory names etc. However, that would be too 
 *    complicated and not worth depicting in the implementation. The main idea 
 *    of this algorithm is to use a stack. How you decide to process the input 
 *    string is a personal choice.
 * Space complexity : O(N). Actually, it's 2N because we have the array that 
 *    contains the split components and then we have the stack.
 */

class Solution {
    public String simplifyPath(String path) {
        if(path == null || path.isEmpty()) return "";
        String[] components = path.split("/");
        Stack<String> stack = new Stack<String>();
        for(String directory: components) {
            if(directory.isEmpty() || directory.equals(".")) {
                continue;
            } else if(directory.equals("..")) {
                if(!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.add(directory);
            }
        }
        StringBuilder result = new StringBuilder();
        for(String dir: stack) {
            result.append("/");
            result.append(dir);
        }
        return result.length() > 0? result.toString(): "/";
    }
}
```

{% endtab %}
{% endtabs %}

### Follow up

* Program for longest common directory path - [GFG](https://www.geeksforgeeks.org/program-longest-common-directory-path/)