Skip to content

← leetcode

Remove Sub Folders from the Filesystem

· Medium

LeetCode problem 1233

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;
    }
};

complexity

  • Time: O(n log(n)) where n is the number of elements inside folder
  • Space: O(n)

time taken

  • I FORGOT TO TIME