1233: Remove-Sub-Folders-from-the-Filesystem
Medium
table of contents
Originally, my solution was to sort
folder lexicographically and curate a
hashmap of all the folders.
However, the hashmap is actually unnecessary; the
last element of the ans array is enough. Since after
sorting folder lexicographically, the parent folders will
always end up coming right before the sub-folders
do.
An example would just be an array consisting of
["/a/b","/a","/c/d","/c/d/e","/c/f"]after sorting it lexicographically
["/a","/a/b","/c/d","/c/d/e","/c/f"]meaning the parent folders like "/a" and
"/c/d/" always come right before the sub-folders.
Therefore, since they will also be the most recently
added string into the ans array,
code
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(), folder.end());
vector<string> ans;
for (string& s : folder) {
if (ans.empty() || s.find(ans.back() + '/') != 0) {
ans.push_back(s);
}
}
return ans;
}
};