1350. Remove Sub Folders From The Filesystem¶

Difficulty: Medium

1350. Remove Sub-Folders from the Filesystem

Medium

Given a list of folders folder, return the folders after removing all sub-folders in those folders. You may return the answer in any order.

If a folder[i] is located within another folder[j], it is called a sub-folder of it. A sub-folder of folder[j] must start with folder[j], followed by a "/". For example, "/a/b" is a sub-folder of "/a", but "/b" is not a sub-folder of "/a/b/c".

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⁴
2 <= folder[i].length <= 100
folder[i] contains only lowercase letters and '/'.
folder[i] always starts with the character '/'.
Each folder name is unique.

Solution¶

class Solution {
    static class custom_sort implements Comparator<String> {
        @Override
        public int compare(String first , String second) {
            return Integer.compare(first.length() , second.length());
        }
    }
    public List<String> removeSubfolders(String[] folder) {
        int n = folder.length;
        List<String> res = new ArrayList<>();
        Arrays.sort(folder, new custom_sort());
        int vis[] = new int[n];
        for (int i = 0; i < n; i++) {
            if (vis[i] == 1) 
                continue;
            res.add(folder[i]);
            vis[i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (check(folder[i] , folder[j])) 
                    vis[j] = 1;
            }
        }
        return res;
    }
    private boolean check(String first, String second) {
        int n = first.length();
        int m = second.length();
        if (n == m) {
            if (second.startsWith(first)) 
                return true;
        }
        for (int i = 0; i < Math.min(n , m); i++) {
            if (first.charAt(i) != second.charAt(i)) 
                return false;
        }
        if (second.charAt(n) == '/') 
            return true;
        return false;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here