tags: Trie
Given a list of folders, remove all sub-folders in those folders and return in any order the folders after removing.
If a folder[i] is located within another folder[j], it is called a sub-folder of it.
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 * 10^4 2 <= folder[i].length <= 100 folder[i] contains only lowercase letters and '/' folder[i] always starts with character '/' Each folder name is unique.
// 552ms, 6%
const int CHAR_COUNT = 27;
class Trie {
private:
Trie* buf[CHAR_COUNT];
bool isWord;
public:
Trie() {
isWord = false;
fill(buf, buf + CHAR_COUNT, nullptr);
}
void insert(const string& s) {
Trie* cur = this;
for (const auto& _c : s) {
int c = _c == '/'? CHAR_COUNT - 1: (_c - 'a');
if (!cur->buf[c]) cur->buf[c] = new Trie();
cur = cur->buf[c];
}
cur->isWord = true;
}
bool hasPrefix(const string& s) {
Trie* cur = this;
for (int i = 0; i < s.size() && cur; i++) {
const auto& _c = s[i];
if (_c == '/' && cur->isWord)
return true;
int c = _c == '/'? CHAR_COUNT - 1: (_c - 'a');
cur = cur->buf[c];
}
return false;
}
};
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
Trie tree;
for (const auto& s : folder)
tree.insert(s);
vector<string> res;
res.reserve(folder.size());
for (const auto& s : folder) {
if (!tree.hasPrefix(s))
res.push_back(s);
}
return res;
}
};
// 360ms, 19%
class Solution {
bool prefixMatch(const string& a, const string& b) {
int cc = 0;
int i = 0;
for (; i < min(a.size(), b.size()); i++) {
if (a[i] == b[i]) cc++;
else break;
}
return cc == a.size() && (i < b.size() && b[i] == '/');
}
public:
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(), folder.end());
int i = 0;
vector<string> res;
res.reserve(folder.size());
while (i < folder.size()) {
const auto& cur = folder[i];
res.push_back(cur);
int j = i + 1;
for (; j < folder.size(); j++) {
bool match = prefixMatch(cur, folder[j]);
if (!match)
break;
}
i = j;
}
return res;
}
};