In this chapter, we will solve a very interesting and real world problem using stacks.
In this chapter, we will solve a very interesting and real world problem using stacks.
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:
'/'
.'/'
.'/'
.'.'
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.
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/"
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.
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
O(N)
as we are iterating the whole string.
O(N)
in the worst case as we may end up storing almost all the directories in the stack.
© 2022 - All Rights Reserved.