Formatted question description: https://leetcode.ca/all/1233.html

1233. Remove Sub-Folders from the Filesystem

Level

Medium

Description

Given a list of folders, remove all sub-folders in those folders and return in any order the folders after removing.

If a folder[i] is located within another folder[j], it is called a sub-folder of it.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.

Example 1:

Input: folder = [“/a”,”/a/b”,”/c/d”,”/c/d/e”,”/c/f”]

Output: [“/a”,”/c/d”,”/c/f”]

Explanation: Folders “/a/b/” is a subfolder of “/a” and “/c/d/e” is inside of folder “/c/d” in our filesystem.

Example 2:

Input: folder = [“/a”,”/a/b/c”,”/a/b/d”]

Output: [“/a”]

Explanation: Folders “/a/b/c” and “/a/b/d/” will be removed because they are subfolders of “/a”.

Example 3:

Input: folder = [“/a/b/c”,”/a/b/ca”,”/a/b/d”]

Output: [“/a/b/c”,”/a/b/ca”,”/a/b/d”]

Constraints:

  • 1 <= folder.length <= 4 * 10^4
  • 2 <= folder[i].length <= 100
  • folder[i] contains only lowercase letters and ‘/’
  • folder[i] always starts with character ‘/’
  • Each folder name is unique.

Solution

Create a class Folder that contains the current folder’s name and a list of its children, which also have type Folder.

Sort the array folder. Use a list to store the root folders that are objects of type Folder. For each folderName in folder, if the list is empty, create a new folder using folderName and add it to the list. Otherwise, loop over existing roots and try to add a subfolder. If a subfolder is added successfully, then it is a subfolder. Otherwise, create a new folder as a root folder and add it to the list.

Finally, loop over the list and add the roots’ names to the result list and return.

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<Folder> roots = new ArrayList<Folder>();
        for (String folderName : folder) {
            if (roots.isEmpty()) {
                Folder newFolder = new Folder(folderName);
                roots.add(newFolder);
            } else {
                boolean flag = false;
                for (Folder root : roots) {
                    boolean addSubfolder = addSubfolder(root, folderName);
                    if (addSubfolder) {
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    Folder newFolder = new Folder(folderName);
                    roots.add(newFolder);
                }
            }
        }
        List<String> remainingFolders = new ArrayList<String>();
        for (Folder root : roots) {
            String rootName = root.folderName;
            remainingFolders.add(rootName);
        }
        return remainingFolders;
    }

    public boolean addSubfolder(Folder root, String folderName) {
        String rootName = root.folderName;
        if (!folderName.contains(rootName))
            return false;
        String[] rootNameArray = rootName.split("/");
        String[] folderNameArray = folderName.split("/");
        if (rootNameArray.length == folderNameArray.length)
            return false;
        else {
            root.addSubfolder(folderName);
            return true;
        }
    }
}

class Folder {
    String folderName;
    List<Folder> children;

    public Folder() {
        
    }

    public Folder(String folderName) {
        this.folderName = folderName;
        children = new ArrayList<Folder>();
    }

    public void addSubfolder(String subFolderName) {
        Folder subFolder = new Folder(subFolderName);
        children.add(subFolder);
    }
}

All Problems

All Solutions