Problem

Submissions

Hints & solutions

Discuss

Simplify the Directory

Moderate

0/80

Average time to solve is 22m

Contributed by

18 upvotes

Asked in companies

Problem statement

You are given a path to a file/directory in Unix-style of length N, In a Unix-style file system, a dot(.) refers to the current directory. A double dot(..) refers to the previous directory in reference to the current directory. If there are multiple slashes between two directories you should consider it as a single slash.

Now, for a given directory path as a string, you are required to simplify the same and tell the final destination in the directory structure or the path.

The simplified path should always begin with a slash(/) and there must be a single slash between two directory names. There should not be a trailing slash.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer T which denotes the number of test cases to be run. 

The first and only line of each testcase contains a single string denoting the path .

Output Format:

For each test case, print a string representing a simplified path to the resulting file or directory.

Note:

You are not required to print anything explicitly. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
0 <= N <= 10^5
Where N is the length of the input path.

Time Limit : 1 sec

Sample Input 1:

1
/a/

Sample Output 1 :

/a

Explanation for input 1:

Directory should always start with a slash and there should not be a trailing slash.

Sample Input 2:

2
/a/b/../
/a/./b/../../c/

Sample Output 2 :

/a
/c

Explanation for input 2:

For test case one, as double dot represents the previous directory so going one step back from the current directory(b) is a. 

For the second test case, at first we are at ‘a’, then we encounter a dot(.) then we move to ‘b’, then we have a double dot(..) so double dot means we have to go one step back, so now we will be at ‘a’, then again we have a double dot so going one step back again,  we are at empty directory then we encounter c, so the final answer would be /c.

Hint 1

Think of using a stack.

Approaches (1)

Approach 1

Stack Approach

Initialize a stack that will store the directories.
For every directory between slashes check

a). If it is a dot then continue.

b). If it is double dot then pop the directory from the stack.

c). Else push into the stack.

Now, take an empty string and a temporary stack.
Pop all the elements from the first stack and store into a temporary stack.
Pop all the elements from the temporary stack and store into an answer string and add a slash.
Return the answer string.

Time Complexity

O(N), where N is the length of string, as for every directory we are pushing and popping it once in the stack and temporary stack.

Space Complexity

O(N), Where N is the length of the string, as the stack will take up space.

(100% EXP penalty)

Simplify the Directory

Console