Leetcode: Simplify Path

 This question is asked at Facebook, Amazon, and Microsoft. Given a string path, which is an absolute path (starting with a slash '/') to a file or directory, we want to convert it to the canonical path.

'.' refers to a period or the current directory whereas '..' refers to the directory up a level. Any other format is treated as file/directory names. The canonical path should have the format: 

- The path starts with a single slash '/'.

- Any two directories separated by a single slash '/'. 

- The path does not end with a trailing '/'. 

- The path '...' periods is treated only as file/directory names.

We want to return a simplified canonical path.

Here are 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.

The Solution is using stacks. This is a direct implementation of the most common commands used on all the famous operating systems. There's much more than simply figuring out the smallest path. Our code needs to be able to run properly, but our code needs to handle scenarios like . , ..,  and /.

We will use a tree for this structure.

First, we try to run the command cd /a/b/c/.././././//d

If we add /a/b/c/.. we pop out the subdirectory c off the stack. Now we want to discuss the algorithm with the time complexity O(N).

Here is the algorithm.

First, we initialize a stack that we will be using for our implementation.

Then we split the input string using / as the delimiter, so everything now is a directory name or a special character, and we process them accordingly. 

Once we are one splitting the path, process one component at a time. If the current component is an empty string, do nothing and continue. Do the same if there is a period. However, when there are 2 periods, we have to do some processing, which means we have to go one level up in the directory path. Finally add a component to the stack if not. Then connect all the directory names using /. Surprisingly you can traverse a stack backwards using a for loop.

class Solution {

    public String simplifyPath(String path) {

        //initialize a stack and the directories

        Stack<String> stack = new Stack<String>();

        String[] components = path.split("/");

        for(String directory : components) {

            //ignore the unnecessary elements

            if(directory == "." || directory.isEmpty()) continue;

            //pop the stack back if .. 

            else if (directory.equals("..")) {

                if(!stack.isEmpty()) stack.pop();

            } else {

                //else add the element in the stack to reiterate

                stack.add(directory);

            }

        }

        //print the stack out. 

        StringBuilder result = new StringBuilder();

        for(String dir : stack) {

            result.append("/");

            result.append(dir);

        }

        return result.length() > 0 ? result.toString() : "/";

    }

}