1233. Remove Sub-Folders from the Filesystem

leetcode

#array#csharp#graph#leetcode#sort#string

Task

: 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"]

C# solution

matched/original

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;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<string> RemoveSubfolders(vector<string> folder) {
        sort(folder.begin(), folder.end());
        List<string> result = new List<string>();
        string parent = "";
        
        foreach (var path in folder) {
            if (parent == "" || !path.StartsWith(parent + "/")) {
                parent = path;
                result.push_back(path);
            }
        }
        
        return result;
    }
}

Java solution

matched/original

import java.util.*;

public class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> result = new ArrayList<>();
        String parent = "";
        
        for (String path : folder) {
            if (parent.isEmpty() || !path.startsWith(parent + "/")) {
                parent = path;
                result.add(path);
            }
        }
        
        return result;
    }
}

JavaScript solution

matched/original

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;
};

Explanation

Algorithm

Сортировка папок:

Сначала отсортируем список путей в лексикографическом порядке. Это обеспечит, что при обходе отсортированного списка мы всегда будем проверять родительскую папку перед вложенными папками.

Фильтрация вложенных папок:

Будем использовать переменную для отслеживания текущей родительской папки.

При проходе по отсортированному списку проверим, является ли текущий путь вложенной папкой для отслеживаемой родительской папки. Если нет, обновим отслеживаемую папку и добавим ее в результирующий список.

😎