Solution: Simplify Path

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #71 (Medium): 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 after the last directory name.

Example 2:
Input:	path = "/../"
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.

Example 3:
Input:	path = "/home//foo/"
Output:	"/home/foo"
Explanation:	In the canonical path, multiple consecutive 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:

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.

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('/')
};