71. Simplify Path (String, Stack)

링크: https://leetcode.com/problems/simplify-path/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도: Medium

Intuition

String에 대한 파이썬 내장함수를 알아두면 도움이 된다.

path.split("/") 
# split string with "/". 
# e.g. 
# "/home/" -> ['', 'home', '']
# "/home//foo/" -> ['', 'home', '', 'foo', '']
# "/home/user/Documents/../Pictures" -> ['', 'home', 'user', 'Documents', '..', 'Pictures']

"/".join(stack)
# join array elements with "/"
# e.g.
# ['home', 'user', 'Pictures'] -> home/user/Pictures
# ['...', 'b', 'd'] -> .../b/d

Code

class Solution:
    def simplifyPath(self, path: str) -> str:
        # Initialize a stack
        stack = []

        # Split the input string on "/" as the delimiter
        # and process each portion one by one
        paths = path.split("/")
        for p in paths:
            # A no-op for a "." or an empty string
            if p == "." or not p:
                continue
            # If the current component is a "..", then
            # we pop an entry from the stack if it's non-empt
            if p == "..":
                if stack:
                    stack.pop()
            # Finally, a legitimate directory name, so we add it
            # to our stack
            else:
                stack.append(p)

        # Stich together all the directory names together
        ans = "/" + "/".join(stack)
        return ans

Complexity

Time Complexity: O(N). Splitting N characters into each path -> O(N), process each path one by one -> O(N)

Space Complexity: O(N). 사실 2N인데, stack과 paths에 각각 N개가 들어있기 때문이다.