Сложность: medium
Если дан список папок folder, верните папки после удаления всех вложенных папок в этих папках. Вы можете вернуть ответ в любом порядке. Если папка[i] находится внутри другой папки[j], она называется ее вложенной папкой. Формат пути - это одна или несколько скомбинированных строк вида: '/', за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" являются допустимыми путями, а пустая строка и "/" - нет.
Пример:
Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
👨💻 Алгоритм:
1⃣Сортировка папок:
Сначала отсортируем список путей в лексикографическом порядке. Это обеспечит, что при обходе отсортированного списка мы всегда будем проверять родительскую папку перед вложенными папками.
2⃣Фильтрация вложенных папок:
Будем использовать переменную для отслеживания текущей родительской папки.
3⃣При проходе по отсортированному списку проверим, является ли текущий путь вложенной папкой для отслеживаемой родительской папки. Если нет, обновим отслеживаемую папку и добавим ее в результирующий список.
😎 Решение:
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(), folder.end());
vector<string> result;
string parent = "";
for (const string& path : folder) {
if (parent.empty() || path.find(parent + "/") != 0) {
parent = path;
result.push_back(path);
}
}
return result;
}
};Ставь 👍 и забирай 📚 Базу знаний