Welcome to Subscribe On Youtube

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

  • // OJ: https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/
// Time: O(NlogN * W)
// Space: O(NW)
struct Node {
    unordered_map<string, Node*> m;
    bool end = false;
};
class Solution {
public:
    vector<string> removeSubfolders(vector<string>& A) {
        Node root;
        sort(begin(A), end(A));
        vector<string> ans;
        for (auto &s : A) {
            string word;
            istringstream ss(s);
            auto node = &root;
            bool skip = false;
            while (getline(ss, word, '/') && !skip) {
                if (word.empty()) continue;
                if (node->m.count(word) && node->m[word]->end) skip = true;
                if (!node->m[word]) node->m[word] = new Node();
                node = node->m[word];
            }
            if (skip) continue;
            node->end = true;
            ans.push_back(s);
        }
        return ans;
    }
};

  • class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        ans = [folder[0]]
        for f in folder[1:]:
            m, n = len(ans[-1]), len(f)
            if m >= n or not (ans[-1] == f[:m] and f[m] == '/'):
                ans.append(f)
        return ans

############

# 1233. Remove Sub-Folders from the Filesystem
# https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort(key = len)
        s = set()
        res = []
        
        for f in folder:
            path = f.split("/")[1:]
            full = ""
            for p in path:
                full += p
                if full in s: break
            else:
                s.add(full)
                res.append(f)
    
                
        
        return res

  • func removeSubfolders(folder []string) []string {
	sort.Strings(folder)
	ans := []string{folder[0]}
	for _, f := range folder[1:] {
		m, n := len(ans[len(ans)-1]), len(f)
		if m >= n || !(ans[len(ans)-1] == f[:m] && f[m] == '/') {
			ans = append(ans, f)
		}
	}
	return ans
}

All Problems

All Solutions