1233. Remove Sub-Folders from the Filesystem
Difficulty: Medium
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:
- Sort the folders lexicographically.
- 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.
Solution:
We can utilize a combination of sorting and string comparison. The steps below outline a solution in PHP:
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.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.
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
/**
* @param String[] $folder
* @return String[]
*/
function removeSubfolders($folders) {
...
...
...
/**
* go to ./solution.php
*/
}
// 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:
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.-
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 theresult
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 toresult
.
- If
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.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)