0071._simplify_path.md

71. Simplify Path

难度: Medium

刷题内容

原题连接

• 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"
path = "/a/../../b/../c//.//", => "/c"
path = "/a//b////c/d//././/..", => "/a/b/c"

In a UNIX-style file system, a period ('.') refers to the current directory, so it can be ignored in a simplified path. Additionally, a double period ("..") moves up a directory, so it cancels out whatever the last directory was. For more information, look here: https://en.wikipedia.org/wiki/Path_(computing)#Unix_style

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".

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

非常简单的模拟题，利用一个栈来储存当前的路径。用 "/" 将输入的全路径分割成多个部分，对于每一个部分循环处理：如果为空或者 "." 则忽略，如果是 ".." ，则出栈顶部元素（如果栈为空则忽略），其他情况直接压入栈即可。

beats 100%

class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        stack = []
        for part in path.split("/"):
            if part and part != ".": # 如果为空或者 "." 则忽略
                if part == "..":
                    if stack:
                        stack.pop()
                else:
                    stack.append(part)
        if not stack:
            return "/"
        else:
            return "/" + "/".join(stack)