题目描述
你是一位系统管理员,手里有一份文件夹列表 folder
,你的任务是要删除该列表中的所有 子文件夹,并以 任意顺序 返回剩下的文件夹。
如果文件夹 folder[i]
位于另一个文件夹 folder[j]
下,那么 folder[i]
就是 folder[j]
的子文件夹。
文件夹的「路径」是由一个或多个按以下格式串联形成的字符串: /
后跟一个或者多个小写英文字母。例如,/leetcode
和 /leetcode/problems
都是有效的路径,而空字符串和 /
不是。
样例
输入:folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出:["/a","/c/d","/c/f"]
解释:"/a/b/" 是 "/a" 的子文件夹,而 "/c/d/e" 是 "/c/d" 的子文件夹。
输入:folder = ["/a","/a/b/c","/a/b/d"]
输出:["/a"]
解释:文件夹 "/a/b/c" 和 "/a/b/d/" 都会被删除,因为它们都是 "/a" 的子文件夹。
输入:folder = ["/a/b/c","/a/b/d","/a/b/ca"]
输出:["/a/b/c","/a/b/ca","/a/b/d"]
限制
1 <= folder.length <= 4 * 10^4
2 <= folder[i].length <= 100
folder[i]
只包含小写字母和/
。folder[i]
总是以字符/
起始。- 每个文件夹名都是唯一的。
算法
(排序) $O(nL \log (nL))$
- 把所有字符串按照字典序排序。
- 排序后第一个字符串一定会出现在答案数组中。
- 从第二个字符串开始遍历,每次和答案数组中最后一个字符串进行判定,如果不是答案数组中最后一个字符串的子串,则将其加入答案数组。
时间复杂度
- 排序后扫一遍,故时间复杂度为 $O(nL \log (nL))$。
空间复杂度
- 需要额外 $O(nL)$ 的空间存储答案。
C++ 代码
class Solution {
private:
bool isUnder(const string &x, const string &y) {
const int n = x.size(), m = y.size();
if (n >= m)
return false;
for (int i = 0; i < n; i++)
if (x[i] != y[i])
return false;
return y[n] == '/';
}
public:
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(), folder.end());
const int n = folder.size();
vector<string> ans;
ans.push_back(folder[0]);
for (int i = 1; i < n; i++)
if (!isUnder(ans.back(), folder[i]))
ans.push_back(folder[i]);
return ans;
}
};
妙不可言!
感觉写的稍微有点麻烦,split函数没有太大必要吧,string直接按照位比较就可以了
已简化hh