1233. Remove Sub-Folders from the Filesystem

[mah-shamim]

Topics: Array, String, Depth-First Search, Trie

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

Hint:

1. Sort the folders lexicographically.
2. Insert the current element in an array and then loop until we get rid of all of their subfolders, repeat this until no element is left.

[kovatz]

We can utilize a combination of sorting and string comparison. The steps below outline a solution in PHP:

1. Sort the Folders Lexicographically: Sorting the folder paths in lexicographical order ensures that any sub-folder will follow its parent folder immediately. For example, "/a" will be followed by "/a/b" in the sorted list, allowing us to check for sub-folder relationships easily.

2. Identify and Filter Out Sub-Folders: We can iterate through the sorted list, checking if the current folder path is a sub-folder of the previously added path. If it is, we skip it. If not, we add it to our result list.

3. Implement the Solution in PHP: We keep track of the last folder path added to the result list. If the current folder starts with this last folder and is immediately followed by a /, it’s a sub-folder and should be ignored.

Let's implement this solution in PHP: 1233. Remove Sub-Folders from the Filesystem

<?php
function removeSubfolders($folders) {
    // Step 1: Sort folders lexicographically
    sort($folders);

    // Step 2: Initialize result array
    $result = [];

    // Step 3: Loop through each folder
    foreach ($folders as $folder) {
        // Check if the current folder is a sub-folder of the last folder in result
        if (empty($result) || strpos($folder, end($result) . '/') !== 0) {
            // If it's not a sub-folder, add it to the result
            $result[] = $folder;
        }
    }

    return $result;
}

// Test cases
$folder1 = ["/a","/a/b","/c/d","/c/d/e","/c/f"];
$folder2 = ["/a","/a/b/c","/a/b/d"];
$folder3 = ["/a/b/c","/a/b/ca","/a/b/d"];

print_r(removeSubfolders($folder1)); // Output: ["/a","/c/d","/c/f"]
print_r(removeSubfolders($folder2)); // Output: ["/a"]
print_r(removeSubfolders($folder3)); // Output: ["/a/b/c","/a/b/ca","/a/b/d"]
?>

Explanation:

1. Sorting: The sort() function arranges folders in lexicographical order. This makes it easier to find sub-folder relationships because sub-folders will follow their parent folders directly.

2. Loop through each folder:

   • If result is empty (first iteration) or if the current folder path does not start with the last added folder followed by a /, it is not a sub-folder and is added to the result array.
   • If it does start with the last folder path and has a / immediately following, it’s a sub-folder, and we skip adding it to result.

3. Result: The function returns result, which contains only the root folders, excluding any sub-folders.

This approach is efficient with a time complexity of O(n log n) due to the sorting step, and the linear scan has O(n), making this a good solution for larger inputs within the problem's constraints.

[mah-shamim]

Thanks to solve this problem efficiently

[kovatz]

Thanks