> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/stack/71-simplify-path.md).

# 71 Simplify Path

## 71. [Simplify Path](https://leetcode.com/problems/simplify-path/description/)

## 1. Question

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

## 2. Implementation

思路：根据题目的例子，我们知道" "， ".", ".."这三种情况不会出现在结果里，所以把它们存在HashSet里。如果我们遇到".."， 我们需要返回上一级目录，所以需要利用stack。最后需要将stack的结果用“/"隔开，注意stack存储结果的顺序和实际的结果是相反的。

```java
class Solution {
    public String simplifyPath(String path) {
        Set<String> set = new HashSet<>();
        set.add(".");
        set.add("..");
        set.add("");

        Stack<String> stack = new Stack<>();

        for (String dir : path.split("/")) {
            if (dir.equals("..") && !stack.isEmpty()) {
                stack.pop();
            }
            else if (!set.contains(dir)) {
                stack.push(dir);
            }
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.insert(0, stack.pop());
            res.insert(0, "/");
        }
        return res.length() == 0 ? "/" : res.toString();
    }
}
```

## 3. Time & Space Complexity

时间和空间都是O(n)