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++:

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:

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
}