Home > Article > Backend Development > Remove Sub-Folders from the Filesystem
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.
Example 1:
Example 2:
Example 3:
Constraints:
Hint:
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
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 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.
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:
The above is the detailed content of Remove Sub-Folders from the Filesystem. For more information, please follow other related articles on the PHP Chinese website!