Intuition
- Start by removing unnecessary parts of the path, including more than one slash as well as ending and beginning slashes (you will add the beginning slash back in later)
- Then, examine each part of the path. Using a stack for this purpose, notice that when you encounter a
.., the previous item can be removed. When you see a., don’t add to the stack. Otherwise, add that part to the stack. This handles cases such as...as well, which are valid. - Finally, add back in the initial
/, followed by each part of the stack joined back together with a slash before each part.
Complexity
Runtime
, where N is the number of parts in a path, where a part is the string in between each of the /’s.
Space
to store the parts via a stack.
Code
Beats 100%
class Solution:
def simplifyPath(self, path: str) -> str:
path = re.sub(r"/+","/", path).lstrip("/").rstrip("/") # Replace // with /, and remove last /
back_action = path.split("/")
stack = []
for p in back_action:
if p == "..":
if stack:
stack.pop()
elif p != ".":
stack.append(p)
return "/" + "/".join(stack)- In this version, we directly place the slash in the beginning
Beats 33%
class Solution:
def simplifyPath(self, path: str) -> str:
path = re.sub(r"/+","/", path).lstrip("/").rstrip("/") # Replace // with /, and remove last /
back_action = path.split("/")
stack = []
for p in back_action:
if p == "..":
if stack:
stack.pop()
elif p != ".":
stack.append(p)
if not stack:
return "/"
return "".join("/" + p for p in stack)Cards
START Basic Front: Simplify Path Back: Pre-process removal of unnecessary parts, then use a stack to keep what is important. END