Simplify Path

Leetcode Daily Challenge (12th April, 2023)

12 April, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

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.

Link: https://leetcode.com/problems/simplify-path/description/

Problem Explanation with 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.

Constraints

1 <= path.length <= 3000
path consists of English letters, digits, period '.', slash '/' or '_'.
path is a valid absolute Unix path.

Intuition:-

As we know a folder can be represented by a stack, so we can use a stack to solve this problem.
We can split the path by '/' and then filter out the empty strings and '.' to get the actual folders.
Now simply put the folders in the stack and if we encounter a '..' then pop the top element of the stack.
Finally, we can join the stack elements to get the simplified path.

Solution:-

Create a stack.
Split the path by '/'.
Filter out the empty strings and '.' using filter function and store the result in a list.
Iterate over the list and if the element is not '..' then push it into the stack.
If the element is '..' then pop the top element of the stack.
Finally, join the stack elements with '/' and return the result.
If the stack is empty then return '/'.

Code:-

JAVA Solution

class Solution {
    public String simplifyPath(String path) {
        Stack<String> st = new Stack<>();
        String ans = "",wrd = "";
        path = path + "/";
        for(int i = 0;i<path.length();i++){
            char c = path.charAt(i);
            if(c != '/'){
                wrd += c;
            }
            else{
                if(wrd.equals("..")){
                    if(!st.empty())
                        st.pop();
                    wrd = "";
                    continue;
                }
                if(wrd.equals(".")){
                    wrd = "";
                    continue;
                }
                if(!wrd.equals(""))
                    st.push(wrd);
                wrd = "";
            }
        }
        String m = "",r = "";
        while(!st.empty()){
            r = r + st.pop();
            r = r + "+";
        }
        for(int i = 0;i<r.length();i++){
            char c = r.charAt(i);
            if(c != '+')
                wrd = wrd + c;
            else{
                ans = wrd + ans;
                wrd = "";
                ans = ans + "/";
            }
        }
        ans = "";
        wrd = "";
        for(int i = 0;i<r.length();i++){
            char c = r.charAt(i);
            if(c != '+')
                wrd = wrd + c;
            else{
                ans = "/" + wrd + ans;
                wrd = "";
            }
        }

        if(!ans.equals("/") && ans.length() != 0)
            return ans;
        else
            return "/";
    }
}

Python Solution

class Solution:
    def simplifyPath(self, path: str) -> str:
        st = []
        arr = path.split('/')
        def filterpaths(x):
            return x!='.' and x!=''
        filt_arr = list(filter(filterpaths,arr))
        for i in filt_arr:
            if i != '..':
                st.append(i)
            else:
                if len(st)>0:
                    st.pop()

        print(filt_arr)
        print(st)
        ans = ''
        for i in st:
            ans = ans + '/' + i

        if not ans:
            return '/'
        return ans

Complexity Analysis:-

TIME:-

The time complexity is O(n) where n is the length of the path as we are iterating over the path once.

SPACE:-

The space complexity is O(n) where n is the length of the path as we are using a stack to store the folders.

References:-

Stacks

Connect with me:-

java

python

leetcode

dsa