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