Сложность: 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⃣При проходе по отсортированному списку проверим, является ли текущий путь вложенной папкой для отслеживаемой родительской папки. Если нет, обновим отслеживаемую папку и добавим ее в результирующий список.
😎 Решение:
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public IList<string> RemoveSubfolders(string[] folder) {
Array.Sort(folder);
List<string> result = new List<string>();
string parent = "";
foreach (var path in folder) {
if (parent == "" || !path.StartsWith(parent + "/")) {
parent = path;
result.Add(path);
}
}
return result;
}
}
Ставь 👍 и забирай 📚 Базу знаний