Simplify Path

Problem Statement

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

Example 1:

Input: path = "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

Input: path = "/home//movies/.//./bollywood/../../songs/"
Output: "/home/songs"
Explanation: First you entered into home directory, then to movies, after that there is no meaning of "." and "//",
then you further enterned into bollywood directory and then finally returned back twice by using ".." twice and 
reached in home. And finally enetered into songs. Hence /home/songs is the answer.

Solution

The problem statement in itself is quite confusing if you read it only once. But it’s simple.
Let’s first try to understand the problem statement. Just visualize the below scenario to understand the difference between an absolute path and a canonical path.

So, the absolute path is something that you cover even if you come back to the same node again. A canonical path is something that doesn’t count the repeated path. We hope the above scenario helps you understand this. Let’s understand the algorithm now with the below example.

path = "/home//movies/.//./bollywood/../../songs/"

Algorithm

The algorithm works as follows:

First, we split the absolute path around /. For example:

path = ["home", "", "movies", ".", "", ".", "bollywood", "..", "..", "songs"]

As per the question, except "..", ".", "/", and "", everything will be considered as a directory. Also, "." and "" doesn’t mean anything as they do not make any changes in the present directory. Therefore, we will ignore them whenever our pointer points to "." and "". Now we are left with only ".." which means go to the previous directory. Hence we will make use of stack data structure as we just want to go to the last working directory. Let’s understand this with visualization.

Code

import java.io.*;

class Innoskrit {
    
    public static String simplifyPath(String path) {
        String[] finalPath = path.trim().split("/");
        Stack<String> stack = new Stack<>();
        for(int i  = 0; i < finalPath.length; i++) {
            if(finalPath[i].equals(".") || finalPath[i].equals("")) {
                continue;
            } else if (finalPath[i].equals("..")) {
                if(!stack.isEmpty())
                    stack.pop();
            } else {
                stack.push(finalPath[i]);
            }
        }

        
        String canonicalPath = "";
        while(!stack.isEmpty()) {
            canonicalPath = "/" + stack.pop() + canonicalPath;
        }
        
        return canonicalPath;
    }
    
    public static void main (String[] args) {
        System.out.println(Innoskrit.simplifyPath("/home//movies/.//./bollywood/../../songs/"));
        System.out.println(Innoskrit.simplifyPath("/home/"));
    }
}

class Innoskrit:
    
    def simplify_path(path):
        stack = []
        final_path = path.split("/")
        for d in final_path:
            if d == "." or d == "":
                continue
            elif d == "..":
                if len(stack) != 0:
                    stack.pop()
            else:
                stack.append(d)
            
        canonical_path = "/" + "/".join(stack)
        return canonical_path
        
if __name__ == '__main__':
    print(Innoskrit.simplify_path("/home//movies/.//./bollywood/../../songs/"))
    print(Innoskrit.simplify_path("/home/"))

Output:

/home/songs
/home

Time Complexity

O(N) as we are iterating the whole string.

Space Complexity

O(N) in the worst case as we may end up storing almost all the directories in the stack.