Сложность: 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⃣При проходе по отсортированному списку проверим, является ли текущий путь вложенной папкой для отслеживаемой родительской папки. Если нет, обновим отслеживаемую папку и добавим ее в результирующий список.
😎 Решение:
var removeSubfolders = function(folder) {
folder.sort();
let result = [];
let parent = "";
for (let path of folder) {
if (!parent || !path.startsWith(parent + "/")) {
parent = path;
result.push(path);
}
}
return result;
};Ставь 👍 и забирай 📚 Базу знаний