[Top Interview 150] 71. Simplify Path

Solution)

 

class Solution:
    def simplifyPath(self, path: str) -> str:
        # Split so that we only have the directories
        path = path.split('/')
        
        # res will save canonical path
        res = []

        for directory in path:
            # Need to go to the directory up a level so we pop
            if directory == "..":
                if res:
                    res.pop()
            
            # We're still in the current directory so we don't do anything
            elif directory == '.':
                continue

            # Append directory name to res
            elif directory != '':
                res.append(directory)
            
        # Return res in canonical path format with starting '/'
        return '/' + '/'.join(res)

 
 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)
 
 

Explanation)

 
There is no special logic, we'll just do what the absolute path tells us.
 
If it gives us a directory, we'll go to that directory.
If it gives us "..", we'll go up a level.
If it gives us '.', we'll stay at the current level.
 
How are we going to code this?
We'll iterate the directories in path. As we iterate, we'll have an extra stack that will save the directories. 
 
As we save the directories,
when we're given a directory, we'll add that directory to the stack.
when we're given "..", we'll pop from that stack.
when we're given '.', we'll do nothing to that stack.
 
 

Initialization)
 

Currently path is a string with slashes. I want just the directories without the slashes, so I'm going to use split() method to get rid of slashes. This will give us a list of directories, but there will be some empty strings as well so be aware of that when you code.
 
res will save the directories that will be shown in a canonical path.
 

def simplifyPath(self, path: str) -> str:
        path = path.split('/')
        res = []

 
 

Three conditions)
 

As explained earlier, we'll just follow what path tells us.
 

1. If we're given "..", we'll pop from res so that we can go up a level. However, even though we want to go up a level, we might have reached the root or might not know what the upper level directories are. So, we'll only pop if there exists a directory in res.
2. If we're given '.', we'll continue so that we don't affect res.
3. If we're given a directory, we'll add that to res to update the canonical path.

Once we complete the canonical path in res, we now have to convert that into string. Let's use '/'.join().
 
However, iff we use '/'.join() there won't be a starting slash. So we manually add that to our string canonical path and return. 
 

def simplifyPath(self, path: str) -> str:
        path = path.split('/')
        res = []

        for directory in path:
            if directory == "..":
                if res:
                    res.pop()
            
            elif directory == '.':
                continue

            elif directory != '':
                res.append(directory)
            
        return '/' + '/'.join(res)

 
 
 
I think the problem could have been more explicit in explaining how the path works. I sort of learned how these work and still took me a bit of time to figure what's going on. Other than that, I think this is a perfect problem for practicing stack with an appropriate difficulty.