71 Simplify Path
Given an absolute path for a file (Unix-style), simplify it.
For example,
path=
"/home/"
, =>"/home"
path="/a/./b/../../c/"
, =>"/c"
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".
The Idea: This problem requires some Unix domain knowledge.
.
means current directory, so in terms of a path, it adds nothing and can be ignored. ..
means move up to parent directory, and ...
means move up recursively. Utilizing a stack is a natural solution because moving to a parent directory is equivalently to moving to the previous or most recent element in an array.Complexity: O(n) time and space
class Solution:
def simplifyPath(self, path):
"""
:type path: str
:rtype: str
"""
tokens = [token for token in path.split('/') if token != '' and token != '.']
s = []
for token in tokens:
if token == '..':
if s: # separated ifs for case where '...'
s.pop()
else:
s.append(token)
return '/' + '/'.join(s)
obj = Solution()
print(obj.simplifyPath('/...')) # /...
print(obj.simplifyPath('/../')) # /
print(obj.simplifyPath('/')) # /
print(obj.simplifyPath('/a/./b/../../c/')) # /c
print(obj.simplifyPath('/home//foo/')) # /home/foo
Last modified 4yr ago