---
# System prepended metadata

title: 1233. Remove Sub-Folders from the Filesystem
tags: [C++, LeetCode]

---

# LeetCode 1233. Remove Sub-Folders from the Filesystem

https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/description/

## 題目大意

給定一個資料夾列表 `folder`，以任意順序回傳移除所有子資料夾後的資料夾列表

如果 `folder[i]` 位於 `folder[j]` 之內，則稱其為 `folder[j]` 的子資料夾`folder[j]` 的子資料夾必須以 `folder[j]` 開頭，並緊接著一個 `/`

路徑的格式為一個或多個連接的字串，每個字串由 `/` 開頭，後跟一個或多個小寫英文字母
空字串和 `/` 並非有效路徑

Constraints:

- $1\le$ `folder.length` $\le 4\times 10^4$
- $2\le$ `folder[i].length` $\le 100$
- `folder[i]` 僅包含小寫字母和 `/`
- `folder[i]` 必須以字符 `/` 開頭
- 每個資料夾名稱都是唯一的

## 思考

我們先排序的話，事情就會簡單許多

C++:

```cpp!
class Solution
{
public:
    vector<string> removeSubfolders(vector<string> &folder)
    {
        sort(folder.begin(), folder.end());
        vector<string> ans;
        ans.reserve(folder.size());
        string prev = "";

        for (const string &f : folder)
        {
            if (!prev.empty() && f.find(prev + "/") == 0 && f[prev.length()] == '/')
                continue;
            ans.push_back(f);
            prev = f;
        }

        return ans;
    }
};
```

Go:

```go!
func removeSubfolders(folder []string) []string {
	sort.Strings(folder)
	ans := make([]string, 0, len(folder))
	prev := ""

	for _, f := range folder {
		if prev == "" || !strings.HasPrefix(f, prev+"/") {
			ans = append(ans, f)
			prev = f
		}
	}

	return ans
}
```