Solution: Simplify Path
Tags: algorithms, javascript, leetcode
Published: 2021-02-05 20:09:01

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/simplify-path/discuss/1051217/Javascript-or-Stack-Solution-(Two-Approaches)-w-Explanation-or-beats-100-96).*

---

####[Leetcode Problem #71 (*Medium*): Simplify Path](https://leetcode.com/problems/simplify-path/)####

---

***Description:***

*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.*

*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:***

Example 1:||
|---:|---|
*Input:*|path = "/home/"
*Output:*|"/home"
*Explanation:*|Note that there is no trailing slash<br>after the last directory name.

Example 2:||
|---:|---|
*Input:*|path = "/../"
*Output:*|"/"
*Explanation:*|Going one level up from the root directory is a no-op,<br>as the root level is the highest level you can go.

Example 3:||
|---:|---|
*Input:*|path = "/home//foo/"
*Output:*|"/home/foo"
*Explanation:*|In the canonical path, multiple consecutive<br>slashes are replaced by a single one.

Example 4:||
|---:|---|
*Input:*|path = "/a/./b/../../c/"
*Output:*|"/c"

---

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

---

***Idea:***

The nature of unix paths is that you read them like a set of instructions, from left to right, and the instructions are always in reference to where you currently are, not from where you started. This should immediately bring to mind a **stack** format, where each operation deals with the end of the stack.

If we think of our answer (**ans**) as a stack, then we can think of each segment of the **path** as an operation, either adding something to or removing something from the end of **ans**. The next problem is identifying and isolating each segment.

The easiest way to do this is to **split** the **path** by **'/'**. If we do this, we're left with only four possibilities left to code. If the segment is empty or if the segment is a **'.'**, then **ans** is unchanged. If the segment is a **'..'**, we know to go *back* one directory which we simulate by removing the last element of the stack. If the segment is anything else, we move *into* that directory, simulated by adding that segment as a new entry onto our **ans** stack.

At this point, we can just **return** the path made by joining the remaining **ans** with **'/'**'s  along with a leading **'/'**.

The same result can also be achieved by using a **2-pointer sliding window approach** instead of splitting the input **path**. This way eliminates some of the overhead that the split will add to the execution and can make this code more performant.

To do this, we just start each iteration with **i** at the start of each new segment and **j = i + 1**. Then we slide **j** forward to the beginning of the next segment, **slice** the segment, and deal with it the same as the earlier method. At the end of each iteration, we just move **i** forward to **j**, then **j** forward **1** to be ready for the next iteration.

---

**Javascript Code w/ Split:**
```javascript
var simplifyPath = function(path) {
    path = path.split('/')
    let ans = []
    for (let dir of path) 
        if (!dir || dir === '.') continue
        else if (dir === "..") ans.pop()
        else ans.push(dir)
    return '/' + ans.join('/')
};
```

---

**Javascript Code w/ Sliding Window:**

This approach is not quite as clean, but is more performant.
```javascript
var simplifyPath = function(path) {
    let len = path.length, ans = []
    for (let i = 0, j = 1; i < len; i = j++) {
        while (path[j] !== '/' && j < len) j++
        let dir = path.slice(i+1,j)
        if (!dir || dir === '.') continue
        else if (dir === "..") ans.pop()
        else ans.push(dir)
    }
    return '/' + ans.join('/')
};
```