[LeetCode] 1233. Remove Sub-Folders from the Filesystem

https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/description/?envType=daily-question&envId=2024-10-25

leetcode - Remove Sub-Folders from the Filesystem

문제 유형: 문자열 처리, 그리디, 트라이(Trie)

문제 난이도: Medium

 

문제

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.

 

folders라는 폴더를 의미하는 문자열 리스트가 주어집니다. 모든 서브폴더들을 지운 리스트를 반하시오.

순서는 상관없습니다.

 

문약 folder[i]가 다른 folder[j]에 있다면, 서브폴더 입니다.

예를 들어, "/a/b"는 "/a"의 서브폴더입니다.

 

풀이

처음에는 트라이를 만들어서 모든 폴더들을 트라이에 담고, 노드에 종단점을 찍어서 dfs로 고유한 폴더들만 담았으나, 사실 더 간단한 방법이 있다.

정렬을 하면, 문자열들은 사전순으로 정렬된다.

즉, 사전순 정렬된 문자열들을 순차적으로 읽으면서, 이전 유효한 문자열이 현재 문자열의 서브스트링이 아니면, 최종 답에 포함되고, 이전 유효한 문자열을 업데이트 하면 된다.

 

코드

C++

 

트라이를 이용한 풀이

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class TrieNode {
public:
    string key;
    vector<TrieNode*> children;
    bool isEnd;
    TrieNode(string key) {
        this -> key = key;
        isEnd = false;
    }
};

class Trie {
public:
    TrieNode* root;
    Trie() {
        this -> root = new TrieNode("-");
    }

    void insert(vector<string>& parsed) {
        auto curr = root;
        for(int i = 0; i < parsed.size(); ++i) {
            if(curr -> isEnd) return;
            bool exists = false;
            for(int j = 0; j < curr -> children.size(); ++j) {
                if(curr -> children[j] -> key == parsed[i]) {
                    curr = curr -> children[j];
                    exists = true;
                    break;
                }
            }
            if(!exists) {
                auto newNode = new TrieNode(parsed[i]);
                curr -> children.push_back(newNode);
                curr = newNode;
            }
        }
        curr -> isEnd = true;
    }
};

class Solution {
private:
    void dfs(TrieNode* root, string str, vector<string> &ans) {
        if(root -> isEnd) {
            ans.emplace_back(str);
            return;
        }
        for(int i = 0; i < root -> children.size(); ++i) {
            string newPath = str + "/" + root -> children[i] -> key;
            dfs(root -> children[i], newPath, ans);
        }
    }
    vector<string> parsePath(string path) {
        int n = path.size();
        vector<string> res;
        int left = 1;
        int right = 1;
        while(right < n) {
            while(right < n && path[right] != '/') right++;
            right--;
            res.emplace_back(path.substr(left, right - left+1));
            right+=2;
            left = right;
        }

        return res;
    }
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        Trie* t = new Trie();
        for(const auto &path : folder) {
            auto parsed = parsePath(path);
            t -> insert(parsed);
        }

        vector<string> ans;
        dfs(t -> root, "", ans);
        return ans;
    }
};

정렬을 이용한 풀이

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        int n = folder.size();
        sort(folder.begin(), folder.end());
        vector<string> ans;
        ans.push_back(folder[0]);

        string prev = folder[0];
        for(int i = 1; i < n; ++i) {
            string curr = folder[i];
            if(curr.find(prev + '/') != 0) {
                ans.push_back(curr);
                prev = curr;
            }
        }
        return ans;
    }
};