71.Simplify Path

Tags: [stack]

Com: {fb}

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

Given an absolute path for a file (Unix-style), simplify it.

For example,
path="/home/", =>"/home"
path="/a/./b/../../c/", =>"/c"

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"? In this case, you should return"/".
• Another corner case is the path might contain multiple slashes '/'together, such as"/home//foo/". In this case, you should ignore redundant slashes and return"/home/foo".

Solution: Stack

class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        if not path:
            return '/'

        sub_paths = [x.strip() for x in path.split('/') if x and x.strip()]
        stack = []
        for sub_path in sub_paths:
            if sub_path == '.':
                continue
            if sub_path == '..':
                if stack:
                    stack.pop()
                continue

            stack.append('/{}'.format(sub_path))

        if not stack:
            return '/'

        result = []
        while stack:
            result.append(stack.pop())
        result.reverse()
        return ''.join(result)

Revelation:

• In Python, the 'split' gives the result like following:

s = '/home/    /linux/     /good'
arr = s.split('/')
arr
['', 'home', '    ', 'linux', '     ', 'good']

• In Python, if there is nothing before the 'delimiter', the Python will give it an empty string. If there is nothing after the 'delimiter', Python also will give it an empty string.

Note:

• Time complexity = O(n), n is the length of the given path.
• Space complexity = O(n), n is the length of the given path.