Ctrl K

Чистка папок-близнецов

Сложная
После сбоя синхронизации в файловой системе развелись копии папок. Дан список folders: каждый элемент — путь к папке в виде списка имён, например ["home", "me", "notes"] означает /home/me/notes. Две папки (на любой глубине, не обязательно на одном уровне) называются **близнецами**, если у них непустое содержимое и оно устроено одинаково: те же имена вложенных папок, а внутри них — снова одинаковая структура, и так до самого низа. Имена самих папок-близнецов значения не имеют. Все папки, у которых есть хотя бы один близнец, помечаются, и удаляются вместе со всем содержимым. Удаление проходит один раз: если после него какие-то папки стали одинаковыми, их уже не трогают. Верните пути всех оставшихся папок в любом порядке.
Пример 1
folders=[["img"], ["img", "raw"], ["music"], ["music", "raw"], ["docs"]] → [['docs']]

В /img и /music лежит по одной пустой папке raw — их содержимое совпадает, обе удаляются вместе с raw. /docs пуста, а пустые папки близнецами не считаются, так что она остаётся.

Пример 2
folders=[["a"], ["a", "x"], ["a", "x", "z"], ["b"], ["b", "y"], ["b", "y", "z"], ["b", "w"]] → [['a'], ['b', 'w'], ['b']]

/a/x и /b/y обе содержат только пустую z — они близнецы и удаляются. После этого /a пуста, а в /b осталась w, но повторной проверки нет. Остаются /a, /b и /b/w.

Ограничения
  • 1 ≤ len(folders) ≤ 2·10⁴
  • 1 ≤ len(folders[i]) ≤ 500
  • 1 ≤ длина имени ≤ 10, имена из строчных латинских букв и цифр
  • Суммарная длина всех имён ≤ 2·10⁵
  • Пути не повторяются
  • Для каждой папки не в корне её родитель тоже есть в списке
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиВсе способы расставить пробелы СложнаяСклеить в палиндром СложнаяСлова для головоломок СложнаяСлова-рамки СложнаяПалиндромные поддеревья Сложная
загружаем Python…
Вход
folders=[["img"], ["img", "raw"], ["music"], ["music", "raw"], ["docs"]]
Ожидается
[['docs']]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 42 теста на сервере, включая скрытые.